PDA

View Full Version : Series and reductions question

Snakeboy
10-16-2014, 01:54 PM
Hey Richard and all :yo:

So I understand that there is nothing special about Fibonacci numbers having consecutive terms with a ratio tending to Phi, as this is a property of any series of numbers following the same algorithm of adding each term to the previous term, here I chose an arbitrary number ( the number of users online when I logged in, 461 users )

461, 922, 1383, 2305, 3688, 5993, 9681, 15674, 25355, 41029, 66384, 107413, 173797, 281210, 455007, 736217, 1191224, 1927441, 3118665, 5046106, 8164771, 13210877, 21375648, 34586525 , 55962173, 90548698, 146510871, 237059569

The ratio between the 23rd and 24th terms = ( 34586525 / 21375648 ) = 1.618033988...

There is a 24 digit repeating series that is given by reducing Fibonacci numbers to their digital roots, this is the product of reduction to digital roots, no matter the size of the terms

This property of a 24 digit repeating string seems to be inherent to all strings following the same rule, below the 24th term is in brackets

461, 922, 1383, 2305, 3688, 5993, 9681, 15674, 25355, 41029, 66384, 107413, 173797, 281210, 455007, 736217, 1191224, 1927441, 3118665, 5046106, 8164771, 13210877, 21375648, { 34586525 }, 55962173, 90548698, 146510871, 237059569

Accompanying 24th term digital root in brackets

2, 4, 6, 1, 7, 8, 6, 5, 9, 7, 9, 7, 7, 5, 3, 8, 9, 1, 3, 4, 7, 2, 9, {2}, 2, 4, 6, 1...

The series starts over

It's not the same series you get by reducing the Fibonacci numbers, yet it's still a repeating series of the same 24 terms

Any ideas as to why this is true ? Or, alternately, is it not true for all series following the same steps ( a 24 term repeating series ) ?

I know you like puzzles, Richard, so I thought I'd ask you :D

Richard Amiel McGough
10-16-2014, 07:53 PM
It's not the same series you get by reducing the Fibonacci numbers, yet it's still a repeating series of the same 24 terms

Any ideas as to why this is true ? Or, alternately, is it not true for all series following the same steps ( a 24 term repeating series ) ?

I know you like puzzles, Richard, so I thought I'd ask you :D
Hey there Snakeboy! :yo:

Thanks for the interesting puzzle. You are correct, I do enjoy them.

I've spent an hour pondering it and Googled around a bit. The pattern is well known, but I haven't seen an explanation yet.

Now you've got me hooked. I'll let you know if I find anything.

Richard

Richard Amiel McGough
10-16-2014, 09:21 PM
OK, I figured it out. It's really quite simple. The formula for a digital root dr(n) is:

dr(n) = 1 + [(n-1)mod 9]

The offset is needed so we get a 1 rather than a 0 when the number is divisible by 9.

To understand what's going on, we need to know how to add the following rule. The digital root of a sum of two numbers is equal to the sum of the digital roots of those two numbers:

dr(a + b) = dr((dr(a) + dr(b))

Therefore, the sequence of digital roots follows a similar rule as the Fibonacci sequence, i.e.

dr(fn) = dr(dr(fn-1) + dr(fn-2))

This is implies that the sequence will repeat if two successive Fibonacci numbers have the same digital roots as the first two. In the case of the standard Fibonacci sequence, this means the sequence will repeat if two successive Fibonacci numbers have a digital root of 1. The necessary condition for this to happen is that the two previous Fibonacci numbers have the values 1 and 9, which is what we see in the last two digits of the repeating sequence:

1,1,2,3,5,8,4,3,7,1,8,9,8,8,7,6,4,1,5,6,2,8,1,9

The same math applies to any sequence that follows the Fibonacci rule. The the Pidgeon Hole Principle implies the sequences must eventually repeat because there are only 92 = 81 possible pairs. I just found a very simple proof here (http://math.stackexchange.com/questions/631171/proof-that-fibonacci-sequence-modulo-m-is-periodic).

If you ask "But why 24 digits?" my answer is "because that's how the math works out." It's the same kind of question as "Why is 6 equal to 2 x 3?"

There is nothing special about digital roots. They are just arithmetic modulo 9. It doesn't matter what number you use as a modulus, you will get repeating patterns. Here are a few examples, with the first occurrences of the repeated sequences bold:

MOD 2, Length 3: 1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0
MOD 3, Length 8: 1,1,2,0,2,2,1,0,1,1,2,0,2,2,1,0,1,1,2,0,2,2,1,0
MOD 4, Length 6: 1,1,2,3,1,0,1,1,2,3,1,0,1,1,2,3,1,0,1,1,2,3,1,0
MOD 5, Length 20: 1,1,2,3,0,3,3,1,4,0,4,4,3,2,0,2,2,4,1,0,1,1,2,3
MOD 6, Length 24: 1,1,2,3,5,2,1,3,4,1,5,0,5,5,4,3,1,4,5,3,2,5,1,0
MOD 7, Length 16: 1,1,2,3,5,1,6,0,6,6,5,4,2,6,1,0,1,1,2,3,5,1,6,0
MOD 8, Length 12: 1,1,2,3,5,0,5,5,2,7,1,0,1,1,2,3,5,0,5,5,2,7,1,0
MOD 9, Length 24: 1,1,2,3,5,8,4,3,7,1,8,0,8,8,7,6,4,1,5,6,2,8,1,0

Ironically and literally, Mod 2 is the odd man out since that is the only sequence with an odd repeat frequency.

Thanks for the Qs! Twasfun.

:sunny:

Richard

Snakeboy
10-17-2014, 04:48 PM
Damn, that was quick :)

Thanks for the explanation, that's very straightforward :thumb: