All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Strange sequence (Posted on 2005-11-15)
If f(0)=0 and for n>0, f(n)=n-f(f(n-1)),
what is f(1,000,000,000,000)?

Computer solutions welcome,
though a proof would be better!

 See The Solution Submitted by e.g. Rating: 3.1667 (6 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 Solution--computer used thrice... | Comment 1 of 9

... once to get the first few values of f(n); then to use the Sloane encyclopedia; then to evaluate f(1,000,000,000,000).

The program below includes different subroutines to evaluate this function.  The first, function f(n) is defined recursively, just as presented in the puzzle, and was the first implemented, through n of about 50, when it began to slow down.

The first several (starting with f(0) are 0  1  1  2  3  3  4  4  5  6  6  7  8  8  9  9  10  11  11  12  12  13  14  14.

The Online Encyclopedia of Integer Sequences identified this as the Hofstadter G-sequence: a(n)=n-a(a(n-1)). It also gives some formulas for evaluating it without recursion or with minimal recursion or iteration.  The simplest is a(n)=floor(sigma*(n+1)) where sigma=(sqrt(5)-1)/2. That is implemented in the below program as function g(n).

Another method is given as

"Rule of construction for the sequence: a(n) = An, where An denotes the Fibonacci antecessor to (or right shift of) n, which is found by replacing each F(i) in the Zeckendorf expansion (obtained by repeatedly subtracting the largest Fibonacci number you can until nothing remains) by F(i-1) (A1=1). For example: 58 = 55 + 3, so a(58)= 34 + 2 = 36. - Diego Torres (torresvillarroel(AT)hotmail.com), Nov 24 2002"

That rule is implemented in function h(x) below, for the curiosity of it. That will help explain it better.

The program, after adding the faster methods, first produces a comparison for the first 58 values of n:

` n  f(n)  g(n) h(n) 1    1    1    1 2    1    1    1 3    2    2    2 4    3    3    3 5    3    3    3 6    4    4    4 7    4    4    4 8    5    5    5 9    6    6    610    6    6    611    7    7    712    8    8    813    8    8    814    9    9    915    9    9    916   10   10   1017   11   11   1118   11   11   1119   12   12   1220   12   12   1221   13   13   1322   14   14   1423   14   14   1424   15   15   1525   16   16   1626   16   16   1627   17   17   1728   17   17   1729   18   18   1830   19   19   1931   19   19   1932   20   20   2033   21   21   2134   21   21   2135   22   22   2236   22   22   2237   23   23   2338   24   24   2439   24   24   2440   25   25   2541   25   25   2542   26   26   2643   27   27   2744   27   27   2745   28   28   2846   29   29   2947   29   29   2948   30   30   3049   30   30   3050   31   31   3151   32   32   3252   32   32   3253   33   33   3354   33   33   3355   34   34   3456   35   35   3557   35   35   3558   36   36   36`

showing that the given non-recursive and less-recursive methods match the recursively defined function.

Then it uses the evaluation a(n)=floor(sigma*(n+1)) where sigma=(sqrt(5)-1)/2, which finds f(1,000,000,000,000) = 618,033,988,750, which is the answer to this puzzle.

Then it evaluates using the "Fibonacci antecessor" method.  That "Zeckendorf expansion" merely means expressing n as a sum of Fibonacci numbers, always using the largest Fib. number that will fit.  The value of f(n) is then the sum of all the Fibonacci numbers that are the next lower than the ones used to sum to n. For 1,000,000,000,000 and f(1,000,000,000,000) these are:

`956722026041  591286729879 32951280099   20365011074  7778742049    4807526976  1836311903    1134903170   701408733     433494437     9227465       5702887      832040        514229      121393         75025       46368         28657        2584          1597         987           610         233           144          89            55          13             8           3             2           `

The left column sums to 1,000,000,000,000, starting with the largest Fib. number under (or equal) that value, then the largest that is under or equal what is left, etc. until a Fib. number (3 in this case) is left.  The right column consists of the Fib. numbers that are just below the corresponding one on the left (for example, 610 is the Fib. number just prior to 987). They indeed add to 618,033,988,750, confirming the answer to this puzzle.

DECLARE FUNCTION f# (n#)
DECLARE FUNCTION g# (n#)
DECLARE FUNCTION fib# (x#)
DECLARE FUNCTION h# (x#)
DEFDBL A-Z
CLEAR , , 25000

DIM SHARED fi(75)
FOR i = 0 TO 75 ' fib(0) = fib(1) = 1
fi(i) = fib(i)
NEXT

FOR x = 1 TO 58
PRINT x; f(x); g(x); h(x)
' IF x MOD 40 = 0 THEN DO: LOOP UNTIL INKEY\$ > ""
NEXT

PRINT g(1000000000000#)
PRINT h(1000000000000#)

FUNCTION f (n)
IF n = 0 THEN
f1 = 0
ELSE
f1 = n - f(f(n - 1))
END IF
f = f1
END FUNCTION

FUNCTION fib (x)
pf = 0: cf = 1
FOR i = 1 TO x
nf = pf + cf
pf = cf: cf = nf
NEXT
fib = cf
END FUNCTION

FUNCTION g (n)
g = INT((n + 1) * (SQR(5) - 1) / 2)
END FUNCTION

FUNCTION h (x)
tot = x: tot2 = 0
DO
i = 1
DO
IF fi(i) > tot THEN EXIT DO
i = i + 1
LOOP
tot2 = tot2 + fi(i - 2)
tot = tot - fi(i - 1)
IF x > 1000 THEN PRINT USING "##############"; fi(i - 1); fi(i - 2)
LOOP UNTIL tot = 0
h = tot2
END FUNCTION

 Posted by Charlie on 2005-11-15 11:46:21

 Search: Search body:
Forums (0)