Re: Re: Re: Re: Timing

*To*: mathgroup at smc.vnet.net*Subject*: [mg88067] Re: [mg88017] Re: [mg88011] Re: [mg87971] Re: Timing*From*: Andrzej Kozlowski <akoz at mimuw.edu.pl>*Date*: Wed, 23 Apr 2008 04:10:01 -0400 (EDT)*References*: <480A0EE6.3090109@csl.pl> <200804211038.GAA28042@smc.vnet.net> <200804211840.OAA09974@smc.vnet.net> <200804221026.GAA28529@smc.vnet.net>

I wrote: > 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. I meant: So expr clearly an integer since any sum of power A^k+B^k can be expressed as polynomial with integer coefficients in the elementary symmetric functions of A and B. Andrzej Kozlowski On 22 Apr 2008, at 19:26, Andrzej Kozlowski wrote: > 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 >> > >

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

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

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