June 2005 - mathfun@mailman.xmission.com

Re: [math-fun] factoring formal power series
by dasimov＠earthlink.net 23 Jun '05

23 Jun '05

Gene writes: << Factorization is not unique. Let p(x) be any power series with integer coefficients beginning with 1. Then 1/p(x) is also a power series with integer coefficients beginning with 1. Then any factor f(x) can be replaced by p(x) (f(x)/p(x)). Neil wrote: > There are lots of algorithms for factoring in Z[x]. > But what about power series with integer coefficients? > Is there a good algorithm? Knuth Vol 2 is silent. > Any hints would be appreciated! > There are two versions, depending on whether you work to > order n, or with the full power series. . . . >> Still, formal power series Z[[x]] over Z might be a unique factorization domain (and surely this is known to algebraists). The non-uniqueness Gene points out looks like a big pain, but at least so far this is only the non-uniquenss that comes about from multiplication & division by the *units* in Z[[x]]. It looks as though there might be a Euclideanesque "algorithm" to find the GCD of two members of Z[[x]] -- but it typically involves infinitely many steps. Still, if it works that would imply Z[[x]] is a UFD. --Dan

1 0

[math-fun] factoring formal power series
by N. J. A. Sloane 23 Jun '05

23 Jun '05

There are lots of algorithms for factoring in Z[x]. But what about power series with integer coefficients? Is there a good algorithm? Knuth Vol 2 is silent. Any hints would be appreciated! There are two versions, depending on whether you work to order n, or with the full power series. Version 1: Given 2 3 4 5 6 7 8 t3 := 1 + 3 x + 7 x + 17 x + 42 x + 113 x + 321 x + 976 x + 3109 x + 9 10 11 12 10258 x + 34698 x + 119554 x + O(x ), find t1 and t2 such that t1*t2 = t3 (mod x^12). Answer: > t1; 2 3 4 5 6 7 8 9 1 + x + 2 x + 5 x + 14 x + 42 x + 132 x + 429 x + 1430 x + 4862 x 10 11 + 16796 x + 58786 x + ... > t2; 2 3 4 5 6 7 8 9 10 1 + 2 x + 3 x + 5 x + 7 x + 11 x + 13 x + 17 x + 19 x + 23 x + 29 x 11 + 31 x + ... Do any of Maple, Mma, Maxima, PARI, Magma, etc. have a command for factoring in this ring? Version 2 (harder): Factor: 1 + 2*Sum_{m >= 1} x^(m^2) = 1 + 2x + 2x^4 + 2x^9 + 2x^16 + ... Answer: Product_{n >= 1} (1-x^2n)(1+x^(2n-1))^2 Neil Sloane

2 1

[math-fun] Fibs mod n
by Gary McGuire 22 Jun '05

22 Jun '05

Notation: fp(n) = period of Fibs mod n. It all boils down to finding fp(p) for p prime, but that's open. I think all we can say is that fp(p) divides p-1 if p=1 or 4 mod 5. fp(p) divides 2(p+1) if p=2 or 3 mod 5. 2(p+1)/fp(p) has to be odd in this last case. (example: if p is a Mersenne prime =2 or 3 mod 5, then 2(p+1) is a power of 2, so fp(p) must equal 2(p+1).) >the highest ratio i've found of period/n is n=10, period=60 >the smallest ratio i've found of period/n is n=9349, period=38 >(i only generated them up to 10000 for this check) > The max possible value for fp(n)/n is 6 (American Mathematical Monthly Problem E3410, March 1992). See http://www.earlham.edu/~rodrimi/Periods%20of%20Fibonacci%20Sequences%20Mod%… Equality occurs infinitely often. Gary McGuire

1 0

[math-fun] fibonacci period
by Chris Landauer 22 Jun '05

22 Jun '05

hihi, all - the primes for which period mod p is (p-1) are 11,19,31,41,59, ... i.e., not all primes - i also get for other primes mod 3 period 8 2*(p+1) mod 5 period 20 p*(p-1) mod 7 period 16 2*(p+1) mod 11 period 10 p-1 mod 13 period 28 2*(p+1) mod 17 period 36 2*(p+1) mod 19 period 18 p-1 mod 23 period 48 2*(p+1) mod 29 period 14 (p-1)/2 mod 31 period 30 p-1 mod 37 period 76 2*(p+1) mod 41 period 40 p-1 mod 43 period 88 2*(p+1) mod 47 period 32 2*(p+1)/3 mod 53 period 108 2*(p+1) mod 59 period 58 p-1 mod 61 period 60 p-1 mod 67 period 136 2*(p+1) mod 71 period 70 p-1 mod 73 period 148 2*(p+1) mod 79 period 78 p-1 mod 83 period 168 2*(p+1) mod 89 period 44 (p-1)/2 an easy shortcut is to notice that once the value reaches 0 again, the period is that subscript times the multiplicative order of the next non-zero mod n (since the recurrence is linear, the values after the next 0 are multiples of the ones after the first 0) for example, mod 5 the second 0 occurs at 5 and the surrounding value is 3, the positive powers of 3 are 3, 4, 2, 1, which occur adjacent to the subsequent 0's, and the period mod n is 5*4 = 20 the highest ratio i've found of period/n is n=10, period=60 the smallest ratio i've found of period/n is n=9349, period=38 (i only generated them up to 10000 for this check) the function is also not multiplicative, since mod 4 period 6 mod 7 period 16 mod 28 period 48 we also know that the roots of x^2 - x - 1 = 0 mod n are relevant (the discriminant is 5) - so perhaps it all boils down to the behavior of the square root(s) of 5 (mod n) more later, cal

2 1

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