wu :: forums « wu :: forums - Integer Sequence? » Welcome, Guest. Please Login or Register. Sep 26th, 2024, 7:21pm

RIDDLES SITE WRITE MATH! Home Help Search Members Login Register

wu :: forums    riddles    hard (Moderators: william wu, towr, Icarus, Eigenray, ThudnBlunder, Grimbal, SMQ)    Integer Sequence? « Previous topic | Next topic » Pages: 1  Reply Notify of replies Send Topic Print    Author  Topic: Integer Sequence?  (Read 1533 times) Barukh Uberpuzzler     Gender: Posts: 2276 Integer Sequence?   « on: Feb 6th, 2006, 6:29am » Quote Modify The sequence gn is defined iteratively as follows:   g0 = 1 gn = (1 + g02 + .. + gn-12)/n, n = 1, 2, …   Is it true that gn consists of integers only? IP Logged thedkl Newbie     Posts: 18 Re: Integer Sequence?   « Reply #1 on: Feb 7th, 2006, 11:48am » Quote Modify is it true that gn=1 for all n? IP Logged towr wu::riddles Moderator Uberpuzzler Some people are average, some are just mean.     Gender: Posts: 13730 Re: Integer Sequence?   « Reply #2 on: Feb 7th, 2006, 12:46pm » Quote Modify on Feb 7th, 2006, 11:48am, thedkl wrote: is it true that gn=1 for all n? No, e.g. g1 = 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 « Last Edit: Feb 7th, 2006, 1:16pm by towr » IP Logged Wikipedia, Google, Mathworld, Integer sequence DB Barukh Uberpuzzler     Gender: Posts: 2276 Re: Integer Sequence?   « Reply #3 on: Feb 17th, 2006, 12:12am » Quote Modify I would like to revive this thread, as there seem to be some subtleties I don't know how to deal with.   Hint: Use modular arithmetic. IP Logged Barukh Uberpuzzler     Gender: Posts: 2276 Re: Integer Sequence?   « Reply #4 on: Mar 31st, 2006, 8:43am » Quote Modify Somebody's still working on this?   IP Logged towr wu::riddles Moderator Uberpuzzler Some people are average, some are just mean.     Gender: Posts: 13730 Re: Integer Sequence?   « Reply #5 on: Mar 31st, 2006, 2:23pm » Quote Modify Well, not me.. After finding the first few numbers from the sequence I just googled and found an answer. IP Logged Wikipedia, Google, Mathworld, Integer sequence DB ecoist Senior Riddler     Gender: Posts: 405 Re: Integer Sequence?   « Reply #6 on: Apr 2nd, 2006, 10:40am » Quote Modify I ignored this problem until today, and expected to get nowhere with it until I remembered something about the Fibonacci sequence.   I get that gn=f(n+2), where f(k) is the Fibonacci sequence.  Hence gn 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 gi in your iteration is the sum of the squares of the first n+1 Fibonacci numbers. IP Logged Obob Senior Riddler     Gender: Posts: 489 Re: Integer Sequence?   « Reply #7 on: Apr 2nd, 2006, 11:06am » Quote Modify Ecoist, your solution doesn't coincide with towr's computed values for the sequence. IP Logged ecoist Senior Riddler     Gender: Posts: 405 Re: Integer Sequence?   « Reply #8 on: Apr 2nd, 2006, 11:51am » Quote Modify Right!  I'm an idiot! IP Logged Eigenray wu::riddles Moderator Uberpuzzler     Gender: Posts: 1948 Re: Integer Sequence?   « Reply #9 on: Mar 9th, 2007, 8:52am » Quote Modify Another old problem:   Let   sn = 1 + g02 + ... + gn-12 = ngn,   so that   sn+1 = sn + gn2 = sn + (sn/n)2.   Since sn 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 s43 isn't an integer.  To show 43 is the first time this happens is a bit trickier.  If pe | n, then we need to compute sn mod pe.  However, if we know sk mod pa, and pb | k, then we only know sk+1 mod pa-2b, since we divided by k2.  So we need to start by knowing s1 mod pa, where a = e + 2b  = 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 sn is an integer for n<43. IP Logged Pages: 1  Reply Notify of replies Send Topic Print Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium => hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board