The 4^n Polynomial conjecture

[Richard Guy]

If  n  is even, then  4^n + ... + 1 = (4^(n+1) - 1)/3

= (2^(n+1) - 1)(2^n+1) + 1)/3.   R.

On Mon, 17 Nov 2003, Edwin Clark wrote:

> On Mon, 17 Nov 2003, cino hilliard wrote:
> 
> > Hi,
> > 
> > I recently submitted the following.
> > 
> > %I A000001
> > %S A000001
> > 6,21,86,341,1366,5461,21846,87381,349526,1398101,5592406,22369621,89478486,
> > 357913941,1431655766,5726623061,22906492246,91625968981,366503875926,
> > 1466015503701,5864062014806,23456248059221,93824992236886,375299968947541,
> > 1501199875790166,6004799503160661,24019198012642646,96076792050570581,
> > 384307168202282326,1537228672809129301
> > %N A000001 Polynomial numbers of the form 4^n + 4^(n-1) + ... + n mod 2 + 1
> 
> The formula is not clear. I think you mean:
> 
>     (4^n + 4^(n-1) + ... + 4 + 1) + (n mod 2)
> 
> Is this correct?
> 
> > 
> > %C A000001 The 4^n Polynomial conjecture:
> > Base 4 polynomial numbers with constant term = n mod 2 + 1 are composite.
> > Or, 4^n + 4^(n-1) + ... + n mod 2 +1 is composite for all n > 0. For n=0 
> > we
> > have 4^0+1 = 2 prime. 
> 
> Unless I  misunderstand something here's a proof of the conjecture:
> 
> If n is odd then a(n) = 4^n + ... + 4^1 + 2 so is even and not prime.
> If n is even then a(n) = 4^n + ... + 4^1 + 1, that is, is a repunit
> to base 4 and according to Chris Caldwell's repunits page at
> 
> http://primes.utm.edu/glossary/page.php?sort=GeneralizedRepunit
> 
> the only one is 4^1 + 1. But since 1 is not even that's not a problem.
>   
> 
> > Also this appears to be true for powers of 4 in 
> > general.
> > While 32 is not a power of 4, 32^n + 32^(n-1) + ... + n mod 2 + 1 is 
> > composite
> > also.
> > %o A000001 (PARI) trajpolypn(n1) =
> >              {
> >              for(x1=1,n1,
> >              y1 = polypn(4,x1);
> >              print1(y1",")
> >              )
> >              }
> > 
> > polypn(n,p) =
> >           {
> >            x=n;
> >             if(p%2,y=2,y=1);
> >             for(m=1,p,
> >             y=y+x^m;
> >                 );
> >            return(y)
> >            }
> > 
> > Maybe some one can help me prove or disprove the case for 4, 4^k and the 
> > oddball 32.
> > Also 8^n +... produces only the prime 73. It look like another situation of 
> > probability - the
> > larger the numbers get the scarcer the primes.
> > 
> > 
> > Here are a few factorizations for the odd values.
> > 
> > n seq      factors ([p,power;prime,power;..])
> > 2 21 [3, 1; 7, 1]
> > 4 341 [11, 1; 31, 1]
> > 6 5461 [43, 1; 127, 1]
> > 8 87381 [3, 2; 7, 1; 19, 1; 73, 1]
> > 10 1398101 [23, 1; 89, 1; 683, 1]
> > 12 22369621 [2731, 1; 8191, 1]
> > 14 357913941 [3, 1; 7, 1; 11, 1; 31, 1; 151, 1; 331, 1]
> > 16 5726623061 [43691, 1; 131071, 1]
> > 18 91625968981 [174763, 1; 524287, 1]
> > 20 1466015503701 [3, 1; 7, 2; 43, 1; 127, 1; 337, 1; 5419, 1]
> > 22 23456248059221 [47, 1; 178481, 1; 2796203, 1]
> > 24 375299968947541 [11, 1; 31, 1; 251, 1; 601, 1; 1801, 1; 4051, 1]
> > 26 6004799503160661 [3, 3; 7, 1; 19, 1; 73, 1; 87211, 1; 262657, 1]
> > 28 96076792050570581 [59, 1; 233, 1; 1103, 1; 2089, 1; 3033169, 1]
> > 30 1537228672809129301 [715827883, 1; 2147483647, 1]
> > 32 24595658764946068821 [3, 1; 7, 1; 23, 1; 67, 1; 89, 1; 683, 1; 20857, 1; 
> > 5994
> > 79, 1]
> > 
> > Certainly the Mersenne primes appear as factors in some cases but I don't 
> > see a  pattern
> > that would deduce a formula.  I guess we could build a sequence of factors 
> > of terms of the
> > sequence.
> > 
> > my program just completed testing for n up to 10000 without finding a prime.
> > (07:01) gp > trajpolypn(10000,4)
> > (07:35) gp >
> > 
> > Have fun,
> > Cino
> > 
> > _________________________________________________________________
> > Great deals on high-speed Internet access as low as $26.95.  
> > https://broadband.msn.com (Prices may vary by service area.)
> > 
> 
> ------------------------------------------------------------
>     W. Edwin Clark, Math Dept, University of South Florida,
>            http://www.math.usf.edu/~eclark/
> ------------------------------------------------------------
>