Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

A weird little problem

  1. May 2, 2005 #1
    Given n, can we find a triplet a, b, c that fits the following conditions:

    n = a*b+c+5
    abs(a-b+c) is minimum

    but only if
    n>a+b+abs(c)+5

    Where n, a, b are naturals and c is integer.


    For instance in case of n=65, I have a hunch the best choices are:
    a = b = 8
    c = 1


    The background for this problem stems from an esoteric programming language - brainf*** ( http://en.wikipedia.org/wiki/brainf*** ). Specifically, I'm trying to find out the most efficient way of writing up ASCII text strings (numerical values between 32 and 255). You can do it either by using an n number of + signs (basically unary, where 65 would be represented by 65 times the '+' sign). The idea is that multiplying two numbers together would be a more efficient way. The code length would be exactly a+b+abs(c)+5.


    Well, you don't have to get bogged down in the details of the language, but if you have an idea for an answer, algorithm or complexity analisys of the problem, you are most welcome to post it.
     
  2. jcsd
  3. May 3, 2005 #2

    honestrosewater

    User Avatar
    Gold Member

    Unless I'm more tired than I realize, 8*8 + 1 + 5 = 70. For n = 65, I found a = 5, b = 11, c = 5 pretty quickly by just putting things together and simplifying:
    1) ab + c + 5 > a + b + |c| + 5 =
    2) ab + c > a + b + |c|.
    If c > 0, (2) reduces to
    3) ab > a + b
    If c < 0, (2) reduces to
    4) ab > a + b + 2|c|
    And add in
    5) |a - b + c|
    To minimize (5), when c > 0, you want a < b, and when c < 0, you want a > b. And of course, you ideally want (5) to equal 0, and that's easy enough to set up. You can get (5) = 0 for a = b, a > 2, c = 0, n = a2 + 5. Work from there maybe. I don't know how to solve your problem, just thought I'd mention some things. If you continue in this manner, you may find your algorithm. Otherwise, I dunno- did you look at some prime factorizations? [shrug] Good luck.
    Edit: Actually, why not just ditch the constant (n is any number in your sequence, so you can just add 5 back in later). Set c > 0 and a < b. Then I think your problem becomes finding solutions for:
    6) n = ab + c
    7) b - a = c
    8) ab > a + b
    (7) should make (5) = 0. You can try the other way (c < 0) if this doesn't work out. So some things are apparent now- like that c can't equal 0 unless n is a perfect square. Edit: If you play around with (6) and (7), you may discover a familiar form.
     
    Last edited: May 3, 2005
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: A weird little problem
  1. A little problem (Replies: 9)

  2. A weird math problem (Replies: 8)

  3. A very weird problem (Replies: 7)

  4. A little problem (Replies: 7)

Loading...