The 4^n Polynomial conjecture

[Edwin Clark]

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/
------------------------------------------------------------