[Date Index]
[Thread Index]
[Author Index]
Re: Re: Re: Timing
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
>
Prev by Date:
**RE: Re: Player Pro and Packages**
Next by Date:
**Re: Re: Wolfram User Interface Research?**
Previous by thread:
**Re: Re: Timing**
Next by thread:
**Re: Re: Re: Re: Timing**
| |