Re: Re: Re: Timing

*To*: mathgroup at smc.vnet.net*Subject*: [mg88017] Re: [mg88011] Re: [mg87971] Re: Timing*From*: Andrzej Kozlowski <akoz at mimuw.edu.pl>*Date*: Tue, 22 Apr 2008 06:26:19 -0400 (EDT)*References*: <480A0EE6.3090109@csl.pl> <200804211038.GAA28042@smc.vnet.net> <200804211840.OAA09974@smc.vnet.net>

It is easy to prove that expr is an integer. Let A=(3 + 2 Sqrt[2]) and B=3 -2 Sqrt[2]. Then A and B are the roots of x^2 - (A + B) x + A B == 0 // Expand = x^2 - 6 x + 1 == 0 with A+B = 6 and A*B=1. Note also that A-B=4Sqrt[2]. expr is (A^m-B^m)/(4*Sqrt[2])= (A-B)*(A^(m-1) + A^(m-2) B + A^(m-3)B^2+ ...A*B^(m-2)+B^(m-1))/(4 Sqrt[2]) = A^(m-1) + A^(m-2) B + A^(m-3)B^2+ ...A*B^(m-2)+B^(m-1) = (A^(m-1)+B^(m-1)) + (A^(m-2)*B+ A*B^(m-2))+...= (A^(m-1)+B^(m-1) + (A^(m-3)+B^(m-3) + ....) + 1 Here m is 2^(n-1)-1.The 1 is present because A*B // Simplify 1 so the product of the same powers o A and B is 1. So expr clearly an integer since any sum of power A^k+B^k can be expresses as polynomial with integer coefficients in the symmetric functions of A and B. So this does not require any use of Mathematica. The question when this is divisible by 2^n-1 is far from clear. One could try to use something like this: f[n_] := Module[ {prec = Log[10, ((2*Sqrt[2] + 3)^ (2^(n - 1) - 1) - (3 - 2*Sqrt[2])^ (2^(n - 1) - 1))/ ((4*Sqrt[2])*(2^n - 1))], p}, p = N[((2*Sqrt[2] + 3)^ (2^(n - 1) - 1) - (3 - 2*Sqrt[2])^ (2^(n - 1) - 1))/ ((4*Sqrt[2])*(2^n - 1)), prec + $MachinePrecision]; p == Round[p]] Table[f[n], {n, 2, 20}] // Timing {11.4016, {False, True, False, True, False, True, False, False, False, False, False, True, False, False, False, True, False, True, False}} This is at least vastly faster than the OP's version. Andrzej Kozlowski On 22 Apr 2008, at 03:40, W_Craig Carter wrote: > Dear Artur, > The previous method should work (in a very weak interpretation of > work) if you replace the expr with; > > expr = Expand[((3 + 2 Sqrt[2])^(2^(n - 1) - 1) - (3 - > 2 Sqrt[2])^(2^(n - 1) - 1))/(4 Sqrt[2])] > > Note: > > FullSimplify[Together[expr], Element[n, Integers]] > > is considerably simpler > > ((3 + 2*Sqrt[2])^2^(-1 + n)*(-4 + 3*Sqrt[2]) - > (3 - 2*Sqrt[2])^2^(-1 + n)*(4 + 3*Sqrt[2]))/8 > > I can't immediately see that this result should be integer, but I am > getting integers for the first 10 > > t = Table[nexpr /. n -> i, {i, 1, 10}] // Expand > Map[IntegerQ, t] > > > In general, Do is slow compared to Table, but it is the size of the > expression that is the limiting factor here. > > On Mon, Apr 21, 2008 at 9:09 AM, Artur <grafix at csl.pl> wrote: >> Dear Craig, >> My problem is find such numbers n that expression >> >> >> ((3 + 2 Sqrt[2])^(2^(n - 1) - 1) - (3 - 2 Sqrt[2])^(2^(n - 1) - 1))/ >> (4 >> Sqrt[2]) >> is divisable by (2^n - 1) >> >> or another words (2^n - 1) is divisor of ((3 + 2 Sqrt[2])^(2^(n - >> 1) - 1) - >> (3 - 2 Sqrt[2])^(2^(n - 1) - 1))/(4 Sqrt[2]) >> >> My procedure Do[ If[IntegerQ[Expand[((3 + 2 Sqrt[2])^(2^(n - 1) - >> 1) - (3 - >> 2 Sqrt[2])^(2^(n - 1) - 1))/(4 Sqrt[2])]/(2^n - 1)], Print[n]], >> {n, 1, >> 17}] >> >> is extremaly slow (probably Expand function do that as aslowly but >> without >> Expand we don't have integers. I don't have idea how improove them. >> Best wishes >> Artur >> >> >> >> >> >> >> >> >> >> W_Craig Carter pisze: >> >> >> >>> Hello Artur, >>> I am not sure I understand your question: >>> >>> Are you asking for >>> Member[expr,Integers] && Element[n,Integers] >>> for 1 <= n <= 17 ? >>> >>> If so, this may be a hint, although it does not exactly check the >>> above: >>> >>> Map[Element[Rationalize[#, .00000001], Integers] & , >>> Table[expr /. n -> i, {i, 1, 30}]] >>> >>> and it is reasonably fast. This approximate method gets worse for >>> large n; so I don't trust the result except for n=1,3,5 >>> >>> Note, that >>> Map[Element[Rationalize[Expand[#], .00000001], Integers] & , >>> Table[expr /. n -> i, {i, 1, 10}]] >>> >>> Gives a different result and is much slower, thus emphasizing the >>> result for large n. >>> >>> I am curious to see the better solutions.... >>> >>> On Mon, Apr 21, 2008 at 6:38 AM, Artur <grafix at csl.pl> wrote: >>> >>> >>>> Who know how change bellow procedure to received reasonable timing? >>>> >>>> Part: >>>> Expand[((3 + 2 Sqrt[2])^(2^(n - 1) - 1) - (3 - 2 Sqrt[2])^(2^(n - >>>> 1) - >>>> 1))/(4 Sqrt[2])]/(2^n - 1) >>>> is every time integer >>>>> Timing[Do[ If[IntegerQ[Expand[((3 + 2 Sqrt[2])^(2^(n - 1) - 1) - >>>>> (3 - >>>>> 2 Sqrt[2])^(2^(n - 1) - 1))/(4 Sqrt[2])]/(2^n - 1)], >>>>> Print[n]], {n, 1, 17}]] >>>>> >>>> I will be greatfull for any help! (Mayby some N[] or Floor[N[]] or >>>> Int[N[]] will be quickest >>>> >>>> Best wishes >>>> Artur >>>> >>>> >>>> >>>> >>> >>> >>> >>> >>> >> > > > > -- > W. Craig Carter >

**Follow-Ups**:**Re: Re: Re: Re: Timing***From:*Artur <grafix@csl.pl>

**Re: Re: Re: Re: Timing***From:*Andrzej Kozlowski <akoz@mimuw.edu.pl>

**References**:**Re: Timing***From:*Artur <grafix@csl.pl>

**Re: Re: Timing***From:*"W_Craig Carter" <ccarter@mit.edu>