Re: Re: How to do quickest
- To: mathgroup at smc.vnet.net
- Subject: [mg73076] Re: [mg73056] Re: [mg73035] How to do quickest
- From: Daniel Lichtblau <danl at wolfram.com>
- Date: Thu, 1 Feb 2007 03:35:10 -0500 (EST)
- References: <epf93g$buf$1@smc.vnet.net> <200701290939.EAA12706@smc.vnet.net> <200701301200.HAA16288@smc.vnet.net> <45BF5CAE.6060602@wolfram.com> <200701310536.AAA17003@smc.vnet.net>
Daniel Lichtblau wrote:
> Daniel Lichtblau wrote:
>
>>Artur wrote:
>>
>>
>>>Probably these procedure isn't possible to do much quicker because
>>>limit is time of single PrimeQ checking but mayby somebody is able do
>>>some quickest (these procedure looking for prime numbers of the form
>>>1+4+4^2+4^3+...4^x (mayby number 5 is only one such number ???):
>>>
>>>a = {}; k = 0; Timing[Do[k = k + 4^x; If[
>>> PrimeQ[k], Print[k]; AppendTo[a, k]], {x, 0, 10000}]; a]
>>>
>>>PrimeQ is relatively quick but working only up to upper limit, later
>>>is necessary uses NumberTheory packagae and much more slowest
>>>procedures.
>>>
>>>BEST WISHES
>>>ARTUR
>> [...]
>>Second, there are various classes of values that can be skipped.
>> [...]
>>Perhaps there is an obvious way to rule out all other contenders.
> [...]
> Probably I am still missing a beat here, [...]
Definitely still missing a beat.
Okay, this took a while but it is indeed the case that 5 is the only
prime in your sequence. Here are two ways to show it that I thought of
belatedly. Your numbers are of the form Sum[4^j,{j,0,n}]. Below I'll
switch freely between integer digit representations and the actual values.
(1) Note that the base 2 representation of your numbers is
x = {1,0,1,0,1,...,1,0,1}.
where the nth number has length 2n+1 in this representation (we start at
n=0). Take such a string, shift one place (e.g. multiply by 2), sum with
the original value, add 1, and we get
2*x + x + 1 = {0,0,...,0,1} = 2^(2*n+2).
So we have x = (2^(2*n+2) - 1) / 3.
The numerator of the rhs factors as
(2^(n+1) + 1) * (2^(n+1) - 1).
Since the lhs is an integer it is clear that 3 divides one of these
factors (or just observe that 3 has to divide one of any three
consecutive numbers, and it cannot divide the one in the middle,
2^(n+1)). So the number in question (x, that is) is composite UNLESS one
of these factors is 3. This happens only when n=1.
(2) Here is an approach that uses symbolic computation. Formulate a
recurrence and solve it in closed form. Then see if this factors in some
nice way. We will use the fact that our "base", 4, is a square. We'll
call it k^2 for now (so this method, as with the one above, works for
squares in general and not just for 4).
In[36]:= InputForm[x = f[n] /. First[
RSolve[{f[n+1]==f[n]+(k^2)^(n+1),f[0]==1}, f[n], n]]]
Out[36]//InputForm= (-1 + k^(2 + 2*n))/(-1 + k^2)
In[38]:= InputForm[Factor[x]]
Out[38]//InputForm= ((-1 + k^(1 + n))*(1 + k^(1 + n)))/
((-1 + k)*(1 + k))
So we have a nontrivial integer factorization whenever the numerator
factors do not overlap with the denominator factors and neither
numerator factor is the product of the denominator factors. This is
clear when n>1.
Daniel Lichtblau
Wolfram Research