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