MathGroup Archive 2007

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Re: How to do quickest

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 
>> [...]
>>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

  • Prev by Date: Re: sort and positon matrix element help
  • Next by Date: Re: & without #
  • Previous by thread: Re: Re: Re: Re: Remote Kernel does nothing
  • Next by thread: Solve, when I already know 1 solution