Start with 0,0,...,0,1 (n-1 0's and a single 1); thereafter the next term is the sum of the previous n terms, modulus 9. The sequence will repeat; for example, n=2: 0, 1, 1, 2, 3, 5, 8, 4, 3, 7, 1, 8, 0, 8, 8, 7, 6, 4, 1, 5, 6, 2, 8, 1, 0, 1, … (period 24); and n=3: 0, 0, 1, 1, 2, 4, 7, 4, 6, 8, 0, 5, 4, 0, 0, 4, 4, 8, 7, 1, 7, 6, 5, 0, 2, 7, 0, 0, 7, 7, 5, 1, 4, 1, 6, 2, 0, 8, 1, 0, 0, 1, … (period 39). Periods can get quite large; for instance, n=24 has period 421900912158 but, empirically, periods for n= one-less-than-powers-of-three & powers-of-three appear to be not only more manageable but surprisingly regular: {2,3} -> {24,39} {8,9} -> {240,273} {26,27} -> {2184,2271} {80,81} -> {19680,19929} {242,243} -> {177144,177879} {728,729} -> {1594320,1596513} {2186,2187} -> {14348904,14355471} {6560,6561} -> {129140160,129159849} {19682,19683} -> {1162261464,1162320519} Can anyone come up with an exact formulation for these?
Hans, I also have been thinking about that kind of problem, but I think it is very hard to solve. A001175 is a classic version of the problem, but even there we don't have a formula (AFAIK). Will you please enter your new version (and tell me the A-number)? I guess we have both been thinking about A210456! Neil On Thu, Feb 21, 2013 at 1:59 PM, Hans Havermann <gladhobo@teksavvy.com>wrote:
Start with 0,0,...,0,1 (n-1 0's and a single 1); thereafter the next term is the sum of the previous n terms, modulus 9. The sequence will repeat; for example, n=2: 0, 1, 1, 2, 3, 5, 8, 4, 3, 7, 1, 8, 0, 8, 8, 7, 6, 4, 1, 5, 6, 2, 8, 1, 0, 1, … (period 24); and n=3: 0, 0, 1, 1, 2, 4, 7, 4, 6, 8, 0, 5, 4, 0, 0, 4, 4, 8, 7, 1, 7, 6, 5, 0, 2, 7, 0, 0, 7, 7, 5, 1, 4, 1, 6, 2, 0, 8, 1, 0, 0, 1, … (period 39). Periods can get quite large; for instance, n=24 has period 421900912158 but, empirically, periods for n= one-less-than-powers-of-three & powers-of-three appear to be not only more manageable but surprisingly regular:
{2,3} -> {24,39} {8,9} -> {240,273} {26,27} -> {2184,2271} {80,81} -> {19680,19929} {242,243} -> {177144,177879} {728,729} -> {1594320,1596513} {2186,2187} -> {14348904,14355471} {6560,6561} -> {129140160,129159849} {19682,19683} -> {1162261464,1162320519}
Can anyone come up with an exact formulation for these? _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Dear Friends, I have now retired from AT&T. New coordinates: Neil J. A. Sloane, President, OEIS Foundation 11 South Adelaide Avenue, Highland Park, NJ 08904, USA Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com
On 2/21/2013 1:59 PM, Hans Havermann wrote:
Start with 0,0,...,0,1 (n-1 0's and a single 1); thereafter the next term is the sum of the previous n terms, modulus 9. The sequence will repeat; for example, n=2: 0, 1, 1, 2, 3, 5, 8, 4, 3, 7, 1, 8, 0, 8, 8, 7, 6, 4, 1, 5, 6, 2, 8, 1, 0, 1, Â… (period 24); and n=3: 0, 0, 1, 1, 2, 4, 7, 4, 6, 8, 0, 5, 4, 0, 0, 4, 4, 8, 7, 1, 7, 6, 5, 0, 2, 7, 0, 0, 7, 7, 5, 1, 4, 1, 6, 2, 0, 8, 1, 0, 0, 1, Â… (period 39). Periods can get quite large; for instance, n=24 has period 421900912158 but, empirically, periods for n= one-less-than-powers-of-three & powers-of-three appear to be not only more manageable but surprisingly regular:
{2,3} -> {24,39} {8,9} -> {240,273} {26,27} -> {2184,2271} {80,81} -> {19680,19929} {242,243} -> {177144,177879} {728,729} -> {1594320,1596513} {2186,2187} -> {14348904,14355471} {6560,6561} -> {129140160,129159849} {19682,19683} -> {1162261464,1162320519}
Can anyone come up with an exact formulation for these?
That table can be generated by the formula {3^n - 1, 3^n} -> {3^(2*n+1) - 3, 3^(2*n+1) + 3^(n+1) + 3} for n = 1, ..., 9. -- Fred W. Helenius fredh@ix.netcom.com
For n=2, I looked by hand at the dynamics map (x,y) -> (y, x+y), with the addition performed mod 9. There are 81 states. (0,0) creates an orbit of length 1. (0,1), (0,2), and (0,4) initiate orbits of length 24. (0,3) is special, because 3 is a divisor of nine, and it polishes off the remaining 8 states. This suggests a Lagrange-like theorem where we expect the lengths of the big orbits to divide 9^n - 3^n. Let's check n=3. A210456(3) = 39. 9^3 - 3^3 = 729 - 27 = 702. And behold, 39*18 = 702. A210456(4) = 78. 9^4 - 3^4 = 6561 - 81 = 6480. But alas, 78 does not divide 6480. The reason is that we have not provided a complete taxonomy of the orbits of the map (w, x, y, z) -> (x, y, z, w+x+y+z) mod 9. There are clearly more (and more interesting) kinds of orbits possible. Nevertheless, I expect some Lagrange-like theorem to explain *some* of the behavior of A210456. Perhaps we should cut our teeth on a prime modulus? Modulo 3, the corresponding sequence starts out 1, 8, 13, 26 (though I may have made an arithmetic error on my mod-3 quadruplets). Although 8 divides 3^2 - 1 and 13 divides 3^3 - 1, 26 does not divide 3^4 - 1, implying again that there are more kinds of orbits than I have dreamt of, so I need a richer philosophy. On Thu, Feb 21, 2013 at 2:51 PM, Fred W. Helenius <fredh@ix.netcom.com>wrote:
On 2/21/2013 1:59 PM, Hans Havermann wrote:
Start with 0,0,...,0,1 (n-1 0's and a single 1); thereafter the next term is the sum of the previous n terms, modulus 9. The sequence will repeat; for example, n=2: 0, 1, 1, 2, 3, 5, 8, 4, 3, 7, 1, 8, 0, 8, 8, 7, 6, 4, 1, 5, 6, 2, 8, 1, 0, 1, … (period 24); and n=3: 0, 0, 1, 1, 2, 4, 7, 4, 6, 8, 0, 5, 4, 0, 0, 4, 4, 8, 7, 1, 7, 6, 5, 0, 2, 7, 0, 0, 7, 7, 5, 1, 4, 1, 6, 2, 0, 8, 1, 0, 0, 1, … (period 39). Periods can get quite large; for instance, n=24 has period 421900912158 but, empirically, periods for n= one-less-than-powers-of-three & powers-of-three appear to be not only more manageable but surprisingly regular:
{2,3} -> {24,39} {8,9} -> {240,273} {26,27} -> {2184,2271} {80,81} -> {19680,19929} {242,243} -> {177144,177879} {728,729} -> {1594320,1596513} {2186,2187} -> {14348904,14355471} {6560,6561} -> {129140160,129159849} {19682,19683} -> {1162261464,1162320519}
Can anyone come up with an exact formulation for these?
That table can be generated by the formula
{3^n - 1, 3^n} -> {3^(2*n+1) - 3, 3^(2*n+1) + 3^(n+1) + 3}
for n = 1, ..., 9.
-- Fred W. Helenius fredh@ix.netcom.com
______________________________**_________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/**cgi-bin/mailman/listinfo/math-**fun<http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun>
Here are some comments on the sequence mod 9 problem: Let a[i] denote the i-th element of the sequence. Construct the formal power series F(X) = sum_i a_i X^i. Summing up n consecutive elements of a_i corresponds to multiplying F(X) by (X^n-1)/(X-1) (except for the ragged end at the beginning). Standard sort of manipulations yield the formula F(X) = X^{n-1} (X-1)^2/g(X), where g(X) = X^{n+1} - 2 X + 1. Now, in order for a_i to have evenutal period m it's necessary and sufficient that we can write F(X) = a(X)/(X^m-1), for some polynomial a(X). Consider the sequence mod 3. Note that g(X) always has the root X=1. If g(X)/(X-1) is irreducible and primitive (which I would expect happens for a positive fraction of such n, but I can't prove it) then the period is 3^n-1. For n=4 it has a double root at X=1 so the factor of 26 comes from 3^3-1. For n=5 it splits in degrees (1,2,3), generically would expect a period of lcm(3^2-1,3^3-1) = 104. Also note that for n = 1 mod 3 that g(X) has (at least) a double root at X=1, so that one needs to make that correction all the time. For n=10, the other factors have degree 2 and 7, so one expects the period there to be lcm(3^2-1,3^7-1). Victor On Thu, Feb 21, 2013 at 3:25 PM, Allan Wechsler <acwacw@gmail.com> wrote:
For n=2, I looked by hand at the dynamics map (x,y) -> (y, x+y), with the addition performed mod 9.
There are 81 states. (0,0) creates an orbit of length 1. (0,1), (0,2), and (0,4) initiate orbits of length 24. (0,3) is special, because 3 is a divisor of nine, and it polishes off the remaining 8 states. This suggests a Lagrange-like theorem where we expect the lengths of the big orbits to divide 9^n - 3^n. Let's check n=3.
A210456(3) = 39. 9^3 - 3^3 = 729 - 27 = 702. And behold, 39*18 = 702.
A210456(4) = 78. 9^4 - 3^4 = 6561 - 81 = 6480. But alas, 78 does not divide 6480. The reason is that we have not provided a complete taxonomy of the orbits of the map (w, x, y, z) -> (x, y, z, w+x+y+z) mod 9. There are clearly more (and more interesting) kinds of orbits possible. Nevertheless, I expect some Lagrange-like theorem to explain *some* of the behavior of A210456.
Perhaps we should cut our teeth on a prime modulus? Modulo 3, the corresponding sequence starts out 1, 8, 13, 26 (though I may have made an arithmetic error on my mod-3 quadruplets). Although 8 divides 3^2 - 1 and 13 divides 3^3 - 1, 26 does not divide 3^4 - 1, implying again that there are more kinds of orbits than I have dreamt of, so I need a richer philosophy.
On Thu, Feb 21, 2013 at 2:51 PM, Fred W. Helenius <fredh@ix.netcom.com>wrote:
On 2/21/2013 1:59 PM, Hans Havermann wrote:
Start with 0,0,...,0,1 (n-1 0's and a single 1); thereafter the next term is the sum of the previous n terms, modulus 9. The sequence will repeat; for example, n=2: 0, 1, 1, 2, 3, 5, 8, 4, 3, 7, 1, 8, 0, 8, 8, 7, 6, 4, 1, 5, 6, 2, 8, 1, 0, 1, … (period 24); and n=3: 0, 0, 1, 1, 2, 4, 7, 4, 6, 8, 0, 5, 4, 0, 0, 4, 4, 8, 7, 1, 7, 6, 5, 0, 2, 7, 0, 0, 7, 7, 5, 1, 4, 1, 6, 2, 0, 8, 1, 0, 0, 1, … (period 39). Periods can get quite large; for instance, n=24 has period 421900912158 but, empirically, periods for n= one-less-than-powers-of-three & powers-of-three appear to be not only more manageable but surprisingly regular:
{2,3} -> {24,39} {8,9} -> {240,273} {26,27} -> {2184,2271} {80,81} -> {19680,19929} {242,243} -> {177144,177879} {728,729} -> {1594320,1596513} {2186,2187} -> {14348904,14355471} {6560,6561} -> {129140160,129159849} {19682,19683} -> {1162261464,1162320519}
Can anyone come up with an exact formulation for these?
That table can be generated by the formula
{3^n - 1, 3^n} -> {3^(2*n+1) - 3, 3^(2*n+1) + 3^(n+1) + 3}
for n = 1, ..., 9.
-- Fred W. Helenius fredh@ix.netcom.com
______________________________**_________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/**cgi-bin/mailman/listinfo/math-**fun<http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun>
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Here's an addition to what I said: If c is a primitive k-th root of 1 over GF(3), and c is a root of g_n(X) = X^{n+1} - 2 X + 1, then it's also a root of g_{n+rk}(X) for any r, so that all the irreducible factors of g_n(X) persist in the congruence class mod k. So, for example, since there's an irreducible factor of degree 2, corresponding to an 8th root of unity for n=2, one expects that for n = 2 + 8*r there will also be such a factor. Victor On Fri, Feb 22, 2013 at 10:08 AM, Victor Miller <victorsmiller@gmail.com> wrote:
Here are some comments on the sequence mod 9 problem:
Let a[i] denote the i-th element of the sequence. Construct the formal power series F(X) = sum_i a_i X^i.
Summing up n consecutive elements of a_i corresponds to multiplying F(X) by (X^n-1)/(X-1) (except for the ragged end at the beginning). Standard sort of manipulations yield the formula
F(X) = X^{n-1} (X-1)^2/g(X), where g(X) = X^{n+1} - 2 X + 1.
Now, in order for a_i to have evenutal period m it's necessary and sufficient that we can write
F(X) = a(X)/(X^m-1), for some polynomial a(X). Consider the sequence mod 3. Note that g(X) always has the root X=1. If g(X)/(X-1) is irreducible and primitive (which I would expect happens for a positive fraction of such n, but I can't prove it) then the period is 3^n-1. For n=4 it has a double root at X=1 so the factor of 26 comes from 3^3-1. For n=5 it splits in degrees (1,2,3), generically would expect a period of lcm(3^2-1,3^3-1) = 104.
Also note that for n = 1 mod 3 that g(X) has (at least) a double root at X=1, so that one needs to make that correction all the time. For n=10, the other factors have degree 2 and 7, so one expects the period there to be lcm(3^2-1,3^7-1).
Victor
On Thu, Feb 21, 2013 at 3:25 PM, Allan Wechsler <acwacw@gmail.com> wrote:
For n=2, I looked by hand at the dynamics map (x,y) -> (y, x+y), with the addition performed mod 9.
There are 81 states. (0,0) creates an orbit of length 1. (0,1), (0,2), and (0,4) initiate orbits of length 24. (0,3) is special, because 3 is a divisor of nine, and it polishes off the remaining 8 states. This suggests a Lagrange-like theorem where we expect the lengths of the big orbits to divide 9^n - 3^n. Let's check n=3.
A210456(3) = 39. 9^3 - 3^3 = 729 - 27 = 702. And behold, 39*18 = 702.
A210456(4) = 78. 9^4 - 3^4 = 6561 - 81 = 6480. But alas, 78 does not divide 6480. The reason is that we have not provided a complete taxonomy of the orbits of the map (w, x, y, z) -> (x, y, z, w+x+y+z) mod 9. There are clearly more (and more interesting) kinds of orbits possible. Nevertheless, I expect some Lagrange-like theorem to explain *some* of the behavior of A210456.
Perhaps we should cut our teeth on a prime modulus? Modulo 3, the corresponding sequence starts out 1, 8, 13, 26 (though I may have made an arithmetic error on my mod-3 quadruplets). Although 8 divides 3^2 - 1 and 13 divides 3^3 - 1, 26 does not divide 3^4 - 1, implying again that there are more kinds of orbits than I have dreamt of, so I need a richer philosophy.
On Thu, Feb 21, 2013 at 2:51 PM, Fred W. Helenius <fredh@ix.netcom.com>wrote:
On 2/21/2013 1:59 PM, Hans Havermann wrote:
Start with 0,0,...,0,1 (n-1 0's and a single 1); thereafter the next term is the sum of the previous n terms, modulus 9. The sequence will repeat; for example, n=2: 0, 1, 1, 2, 3, 5, 8, 4, 3, 7, 1, 8, 0, 8, 8, 7, 6, 4, 1, 5, 6, 2, 8, 1, 0, 1, … (period 24); and n=3: 0, 0, 1, 1, 2, 4, 7, 4, 6, 8, 0, 5, 4, 0, 0, 4, 4, 8, 7, 1, 7, 6, 5, 0, 2, 7, 0, 0, 7, 7, 5, 1, 4, 1, 6, 2, 0, 8, 1, 0, 0, 1, … (period 39). Periods can get quite large; for instance, n=24 has period 421900912158 but, empirically, periods for n= one-less-than-powers-of-three & powers-of-three appear to be not only more manageable but surprisingly regular:
{2,3} -> {24,39} {8,9} -> {240,273} {26,27} -> {2184,2271} {80,81} -> {19680,19929} {242,243} -> {177144,177879} {728,729} -> {1594320,1596513} {2186,2187} -> {14348904,14355471} {6560,6561} -> {129140160,129159849} {19682,19683} -> {1162261464,1162320519}
Can anyone come up with an exact formulation for these?
That table can be generated by the formula
{3^n - 1, 3^n} -> {3^(2*n+1) - 3, 3^(2*n+1) + 3^(n+1) + 3}
for n = 1, ..., 9.
-- Fred W. Helenius fredh@ix.netcom.com
______________________________**_________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/**cgi-bin/mailman/listinfo/math-**fun<http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun>
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
PUZZLE: Find the geometric mean of the unit disk about 0 in the complex plane. (Assume, however, that the interval (-oo, 0] is removed from the plane.) --Dan
I get exp(-1/2). -- Gene
________________________________ From: Dan Asimov <dasimov@earthlink.net> To: math-fun <math-fun@mailman.xmission.com> Sent: Wednesday, April 24, 2013 11:48 AM Subject: [math-fun] Geometric mean puzzle
PUZZLE: Find the geometric mean of the unit disk about 0 in the complex plane.
(Assume, however, that the interval (-oo, 0] is removed from the plane.)
--Dan _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Yup. On 2013-04-24, at 12:14 PM, Eugene Salamin wrote:
I get exp(-1/2).
-- Gene
________________________________ From: Dan Asimov <dasimov@earthlink.net> To: math-fun <math-fun@mailman.xmission.com> Sent: Wednesday, April 24, 2013 11:48 AM Subject: [math-fun] Geometric mean puzzle
PUZZLE: Find the geometric mean of the unit disk about 0 in the complex plane.
(Assume, however, that the interval (-oo, 0] is removed from the plane.)
--Dan _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (7)
-
Allan Wechsler -
Dan Asimov -
Eugene Salamin -
Fred W. Helenius -
Hans Havermann -
Neil Sloane -
Victor Miller