A function is defined recursively by f(0) = 0 and f(n) = n - f(f(n - 1)) for n > 0.
Find f(10,000,000,000).
Here are the first 100 values:
1 1
2 1
3 2
4 3
5 3
6 4
7 4
8 5
9 6
10 6
11 7
12 8
13 8
14 9
15 9
16 10
17 11
18 11
19 12
20 12
21 13
22 14
23 14
24 15
25 16
26 16
27 17
28 17
29 18
30 19
31 19
32 20
33 21
34 21
35 22
36 22
37 23
38 24
39 24
40 25
41 25
42 26
43 27
44 27
45 28
46 29
47 29
48 30
49 30
50 31
51 32
52 32
53 33
54 33
55 34
56 35
57 35
58 36
59 37
60 37
61 38
62 38
63 39
64 40
65 40
66 41
67 42
68 42
69 43
70 43
71 44
72 45
73 45
74 46
75 46
76 47
77 48
78 48
79 49
80 50
81 50
82 51
83 51
84 52
85 53
86 53
87 54
88 55
89 55
90 56
91 56
92 57
93 58
94 58
95 59
96 59
97 60
98 61
99 61
100 62
produced by
n = 0: f(0) = 0
For n = 1 To 100
If f(n - 1) >= 0 And f(n - 1) < n Then
f(n) = n - f(f(n - 1))
Else
Text1.Text = Text1.Text & " stopped" & crlf
Exit Sub
End If
Text1.Text = Text1.Text & n & Str(f(n)) & crlf
DoEvents
Next
That last value, f(100) = 62, would indicate a division by phi, the golden ratio, which does seem to fit with the word "beautiful" in the title.
Some inspection of n/phi shows the integer part of this is offset by 1 from n in evaluating f(n). So using
Str(Int((n + 1) / ((1 + Sqr(5)) / 2)))
to add a column showing floor((n+1)/phi) results in an equal comparison
1 1 1
2 1 1
3 2 2
4 3 3
5 3 3
6 4 4
7 4 4
8 5 5
9 6 6
10 6 6
11 7 7
12 8 8
13 8 8
14 9 9
15 9 9
16 10 10
17 11 11
18 11 11
19 12 12
20 12 12
21 13 13
22 14 14
23 14 14
24 15 15
25 16 16
26 16 16
27 17 17
28 17 17
29 18 18
30 19 19
31 19 19
32 20 20
33 21 21
34 21 21
35 22 22
36 22 22
37 23 23
38 24 24
39 24 24
40 25 25
41 25 25
42 26 26
43 27 27
44 27 27
45 28 28
46 29 29
47 29 29
48 30 30
49 30 30
50 31 31
51 32 32
52 32 32
53 33 33
54 33 33
55 34 34
56 35 35
57 35 35
58 36 36
59 37 37
60 37 37
61 38 38
62 38 38
63 39 39
64 40 40
65 40 40
66 41 41
67 42 42
68 42 42
69 43 43
70 43 43
71 44 44
72 45 45
73 45 45
74 46 46
75 46 46
76 47 47
77 48 48
78 48 48
79 49 49
80 50 50
81 50 50
82 51 51
83 51 51
84 52 52
85 53 53
86 53 53
87 54 54
88 55 55
89 55 55
90 56 56
91 56 56
92 57 57
93 58 58
94 58 58
95 59 59
96 59 59
97 60 60
98 61 61
99 61 61
100 62 62
so f(10,000,000,000) would be floor(10,000,000,001/phi) = 6180339888.
|
|
Posted by Charlie
on 2019-09-03 11:14:16 |
computer observation and solution
