- mathfun@mailman.xmission.com - mailman.xmission.com

Re: [math-fun] Fibonacci mod n question
by dasimov＠earthlink.net 22 Jun '05

22 Jun '05

Marc LeBrun writes: << >=Dan Asimov > ...QUESTION: What is a formula for fp(n) in general? Interesting question, but isn't this basically asking for a formula for the multiplicative order of the matrix [1 1] [0 1] mod n? I understand that's hard for just integers; should we expect it to be easier in matrix land? (but fp(n) sounds like a great candidate for the OEIS!) >> Maybe so about the matrices, but it appears there *is* a formula for fp(n) -- which turns out (no surprise!) to already be in OEIS. The OEIS entry mentions that for a prime p, (*) fp(p) = (p-1). Can someone please explain this notation to me? Thanks. Another comment at that entry is that if n = p1^e1*...* pk^ek, for distinct primes p1,..., pk, then (**) fp(n) = LCM(fp(p1^e1),...,fp(pk^ek)). And I've just noticed strong numerical evidence that for a prime power n = p^r, we have (***) fp(p^r) = p^(r-1) * fp(p). If (***) can be proved, then putting these three equations together gives essentially a formula for all fp(n). (But what the heck does (p-1) mean?!?!?) --Dan

2 2

[math-fun] Self-Junk Fix
by Eric Angelini 22 Jun '05

22 Jun '05

Message published a few minutes ago on rec.puzzles by Ed Pegg (a warm thank you to him): >Here is a potential fix for 3) and 4): > >3') When adding a new integer to the sequence, always choose the > smallest unused positive integer that does not contain any > impossible digits. (0 is impossible from the start; 1 is > impossible once all of 1 through 9 have been used up, etc.). > >4') Whenever we are blocked, go back to the first integer N that was > partly or completely unable to be re-used as a series of length > specifications, and replace it with the smallest unused integer M > of the same length as N that allows the sequence to be extended > further. If there is no valid M, then stop. The question remains: last integer? Best, E.

1 1

[math-fun] Fibonacci mod n question
by dasimov＠earthlink.net 21 Jun '05

21 Jun '05

Consider the Fibonacci sequence F_0 = 0, F_1 = 1, F_2 = 1, ... reduced mod n for fixed n >= 2. This gives a sequence that is clearly periodic, since there are at most n^2 consecutive pairs in Z/nZ. Define fp(n) := the least period of {F_k mod n}. (For example, fp(9) = 24.) QUESTION: What is a formula for fp(n) in general? --Dan Asimov

2 2

Clarificartion Re: [math-fun] Fibonacci mod n question
by dasimov＠earthlink.net 21 Jun '05

21 Jun '05

<< Maybe so about the matrices, but it appears there *is* a formula for fp(n) -- which turns out (no surprise!) to already be in OEIS. >> Here I meant that fp(n) is in OEIS (no surprise), *and* there also appears to be a formula (not in OEIS) for fp(n). --Dan

1 0

RE: [math-fun] Fibonacci mod n question
by dasimov＠earthlink.net 21 Jun '05

21 Jun '05

I wrote: << Consider the Fibonacci sequence F_0 = 0, F_1 = 1, F_2 = 1, ... reduced mod n for fixed n >= 2. . . . Define fp(n) := the least period of {F_k mod n}. QUESTION: What is a formula for fp(n) in general? >> Hmmm, one pattern that seems to hold is that for any prime p, fp(p^2) = p*fp(p). E.g., fp(1) = 1*1, fp(4) = 2*3, fp(9) = 3*8, fp(25) = 5*20, fp(49) = 7*16, fp(121) = 11*10, fp(169) = 13*28. I wonder why. --Dan

1 0

[math-fun] Re: Self-junk
by Eric Angelini 21 Jun '05

21 Jun '05

Jud McCranie : > Doesn't rule 4 violate rule 3? >>3) When adding a new integer to the sequence, put always >> the smallest unused so far >> >>4) Always have in mind that the final sequence must be as >> long as possible -- this explains why the above 8th >> integer is "1122" and not "1111", for instance: "1111" >> would block the sequence very fast: ... yes, strictly speaking, you are right... well... you know what I had in mind... Let's merge the two rules together: 3) When adding a new integer to the sequence, put always the smallest unused so far which allows the final se- quence to be as long as possible. Does it fix the pb ? Best, É.

1 0

[math-fun] Self-junk
by Eric Angelini 21 Jun '05

21 Jun '05

Hello SeqFan and Math-Fun, Can someone find the last term of this (finite) sequence? 1 21 2 11 3 4 111 1122 5 6 7 8 9 22 23 22222 222222 2222222 22222222 222222222 24 25 26 222 27 28 29 32 33 34 35 36 37 38 39 42 43 44 45 46 47 48 49 52 53 54 55 56 57 58 59 62 63 64 65 66 667 68 69 72 2222 73 22223 74 Building rules: 1) The length of each integer is given by the succession of the digits of the sequence itself (first integers have length 1, 2, 1, 2, 1, 1, 3, ...) 2) No two identical integers in the sequence 3) When adding a new integer to the sequence, put always the smallest unused so far 4) Always have in mind that the final sequence must be as long as possible -- this explains why the above 8th integer is "1122" and not "1111", for instance: "1111" would block the sequence very fast: 1 21 2 11 3 4 111 1111 5 6 7 8 9 -- stop, no more available integer of length "1"... Best, É.

2 1

[math-fun] squarefree string draws Sierpinski triangle
by R. William Gosper 21 Jun '05

21 Jun '05

As in my 5 Dec 96 mail (Thanks Rich!), let d(n) be the alternating sum of the nonzero digits of the balanced ternary representation of n. E.g., d(-69) -> -1,0,1,1 -> -1-1+1 = -1. Then d is an odd function, and mod 3 is a squarefree (stutter-free) sequence. For n>=0, 0 1 2 1 0 1 2 0 2 1 0 2 0 1 2 1 0 1 2 0 1 0 2 1 2 0 2 1 0 2 0 1 0 2 1 2 0 1 2 1 0 1 2 0 2 1 0 2 0 1 2 1 0 1 2 0 1 0 2 0 1 2 1 0 2 1 2 0 2 1 0 1 2 0 1 0 2 . . .. Claim: the series of increments (-)^k exp(2 i pi d(k)/3) from k = -(3^n+1)/2 to (3^n-1)/2 draws a self-avoiding polygonal approximation to a curve which sweeps out the triangular Sierpinski "sponge" (or "gasket"). (Try it!) (Spongebob Trianglepants?) For k>=0, it draws a diagonal chain of consecutively larger ones (= the right half of an infinitely large one). There's a lot of interesting math here. I believe n (3 - 1) t ---------- 2 2 i pi d(k) ==== ----------- \ k 3 > (- 1) e / ==== n 3 + 1 k = - ------ 2 f(t) := limit ----------------------------------- n -> oo n 2 is a continuous map of [0,1] onto the closure of the Sierpinski triangle with the unit interval of the real axis as base. This gives us explicit valuations of f where t has a simple ternary expansion, e.g., the rationals. (f(.012101202..._3) = ?) Other claims: n 3 - 1 ------ 2 2 i pi d(k) ==== ----------- \ k 3 > k (- 1) e / ==== n 3 + 1 k = - ------ i sqrt(3) 2 - --------- = limit -------------------------------------, 6 n -> oo n n 2 3 n 3 - 1 ------ 2 2 i pi d(k) ==== ----------- \ 2 k 3 > k (- 1) e / ==== n 3 + 1 k = - ------ 1 2 - = limit --------------------------------------, 8 n -> oo 2 n n 3 2 n 3 - 1 ------ 2 2 i pi d(k) ==== ----------- \ 3 k 3 > k (- 1) e / ==== n 3 + 1 k = - ------ 7 i sqrt 3 2 - ---------- = limit --------------------------------------, ... 432 n -> oo 3 n n 3 2 --rwg PS, Weisstein gives (Thue-Morse sequence) the base 3 squarefree string 0 2 1 0 1 2 0 2 1 2 0 1 0 2 1 0 1 2 0 1 0 2 1 2 0 2 1 0 1 2 0 2 1 2 0 1 0 ... based on renaming the base 4 digits of twice the parity constant. Simpler: Parity(n+1) - Parity(n), where Parity(n) is the usual sum mod 2 of the binary digits of n. (Add 2 mod 3 for the exact match.)

1 1

Re: [math-fun] Ethnomathematics
by Henry Baker 20 Jun '05

20 Jun '05

Interesting, thank you. I think that today's WSJ editorial is significantly more negative than the article you pointed to below. Perhaps Diane's views have changed/evolved since the article below. Perhaps people substantially less talented than the teacher in "Stand & Deliver" have "captured" ethnomathematics and transformed it into another "P.C." initiative. At 08:16 AM 6/20/2005, Kerry Mitchell wrote: >I don't know how similar this is, but it's by the same author and it's on the same subject, and it's freely accessible: > >http://college.hmco.com/currentconflict/students/multicultural/ravitch_arti… > >Kerry >-------------- Original message from Henry Baker <hbaker1(a)pipeline.com>: -------------- > >> In this morning's Wall Street Journal, Diane Ravitch has an editorial on >> "Ethnomathematics". I don't have access to the WSJ Online, so I can't >> include this short editorial, but you can get the gist of "ethnomathematics" >> from this website: >> >> http://www.science.org.au/nova/073/073key.htm

1 0

Re: [math-fun] Ethnomathematics
by lkmitch＠att.net 20 Jun '05

20 Jun '05

I don't know how similar this is, but it's by the same author and it's on the same subject, and it's freely accessible: http://college.hmco.com/currentconflict/students/multicultural/ravitch_arti… Kerry -------------- Original message from Henry Baker <hbaker1(a)pipeline.com>: -------------- > In this morning's Wall Street Journal, Diane Ravitch has an editorial on > "Ethnomathematics". I don't have access to the WSJ Online, so I can't > include this short editorial, but you can get the gist of "ethnomathematics" > from this website: > > http://www.science.org.au/nova/073/073key.htm

1 0