wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Integer Sequence?
        
(Message started by: Barukh on Feb 6^th, 2006, 6:29am)

Title: Integer Sequence?
Post by Barukh on Feb 6^th, 2006, 6:29am

The sequence g_n is defined iteratively as follows:

g₀ = 1
g_n = (1 + g₀² + .. + g_n-1²)/n, n = 1, 2, …

Is it true that g_n consists of integers only?

Title: Re: Integer Sequence?
Post by thedkl on Feb 7^th, 2006, 11:48am

is it true that g_n=1 for all n?

Title: Re: Integer Sequence?
Post by towr on Feb 7^th, 2006, 12:46pm

on 02/07/06 at 11:48:02, thedkl wrote:

is it true that g_n=1 for all n?

No, e.g. g₁ = 2
in fact, the sequence explodes quite rapidly, over a googol in about a dozen step.

1 2
2 3
3 5
4 10
5 28
6 154
7 3520
8 1551880
9 267593772160
10 7160642690122633501504
11 4661345794146064133843098964919305264116096
12 1.8106787177169338e+84
13 2.521967245225415e+167

Title: Re: Integer Sequence?
Post by Barukh on Feb 17^th, 2006, 12:12am

I would like to revive this thread, as there seem to be some subtleties I don't know how to deal with.

Hint: [hide]Use modular arithmetic[/hide].

Title: Re: Integer Sequence?
Post by Barukh on Mar 31^st, 2006, 8:43am

Somebody's still working on this? :-/

Title: Re: Integer Sequence?
Post by towr on Mar 31^st, 2006, 2:23pm

Well, not me.. After finding the first few numbers from the sequence I just googled and found an answer.

Title: Re: Integer Sequence?
Post by ecoist on Apr 2^nd, 2006, 10:40am

I ignored this problem until today, and expected to get nowhere with it until I remembered something about the Fibonacci sequence.

I get that g_n=f(n+2), where f(k) is the Fibonacci sequence. Hence g_n is an integer, for all n[ge]0. This follows from

[sum]_{i=1}^{i=n} f(i)^2 = f(n)f(n+1);

easily proved by induction. The sum of squares of the g_i in your iteration is the sum of the squares of the first n+1 Fibonacci numbers.

Title: Re: Integer Sequence?
Post by Obob on Apr 2^nd, 2006, 11:06am

Ecoist, your solution doesn't coincide with towr's computed values for the sequence.

Title: Re: Integer Sequence?
Post by ecoist on Apr 2^nd, 2006, 11:51am

Right! I'm an idiot!

Title: Re: Integer Sequence?
Post by Eigenray on Mar 9^th, 2007, 8:52am

Another old problem:

Let

s_n = 1 + g₀² + ... + g_n-1² = ng_n,

so that

s_n+1 = s_n + g_n² = s_n + (s_n/n)².

Since s_n grows too fast to compute directly, we compute it mod n, and make sure it's 0.

If n is prime, this is easy:

Code:

For[p = 2, p < 100, p = NextPrime[p],
S[1] = 2;
For[k = 1, k < p, k++,
S[k + 1] = Mod[S[k] + PowerMod[k, -2, p]S[k]^2, p];
];
If[Mod[S[p], p] != 0, Print["S[", p, "]=", S[p]]];
]

S[43]=24 S[61]=12 S[67]=18 S[83]=19

So this shows s₄₃ isn't an integer. To show 43 is the first time this happens is a bit trickier. If p^e | n, then we need to compute s_n mod p^e. However, if we know s_k mod p^a, and p^b | k, then we only know s_k+1 mod p^a-2b, since we divided by k². So we need to start by knowing s₁ mod p^a, where a = e + 2http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gifb = e + 2*# of times p divides (n-1)!. Thus:

Code:

For[n = 2, n <= 43, n++,
fac = FactorInteger[n];
For[i = 1, i <= Length[fac], i++,
(* fac[[i]] = {p, e} *)
p = fac[[i, 1]];
a = fac[[i, 2]] + 2Sum[Floor[(n - 1)/p^k], {k, 1, Log[p, n - 1]}];
S[1] = 2;
For[k = 1, k < n, k++,
b = Log[p, GCD[p^a, k]];
a = a - 2b;
(* S[k + 1] = S[k] + S[k]^2/k^2 *)
S[k + 1] = Mod[S[k] + PowerMod[k/p^b, -2, p^a](S[k]/p^b)^2, p^a];
];
If[S[n] != 0, Print["S[", n, "]=", S[n], " mod ", p^a]];
]
]

gives
S[43]=24 mod 43,
so s_n is an integer for n<43.