[seqfan] A076336

Don Reble djr at nk.ca
Sat Sep 10 06:44:01 CEST 2022


Seqfans:

> %N A076336 (Provable) Sierpinski numbers: odd numbers n such that
>            for all k >= 1 the numbers n*2^k+1 are composite.

> S3: Numbers n such that n*2^k+1 is prime for all k (empty)
> S4: Numbers n such that 2^k+n is prime for all k (empty)

> ...Michael Reid, attempts to show that S3 and S4 are empty:
> If p is a prime divisor of n+1, then for k=p-1, the term
> (either n*2^k+1 or 2^k+n) is a multiple of p
> (and also greater than p, so not prime).

> However, David McAfferty points [out] that for the case S3, this
> argument fails if p is of the form 2^m-1. So it may only be a
> conjecture that the set S3 is empty. -- NJAS, Jun 27 2021

    Did David pass the S4 proof-attempt? No matter...



    For all positive n, there is a k>0 such that n*2^k+1 is composite.
    Cases:
    - n+1 is not a power of two, so has an odd prime factor q: n = mq-1
      Let k=q-1.
      Then n*2^k+1 = (mq-1)*[2^(q-1)]+1 == (mod q) -1*1 + 1 == 0.
      And n*2^k+1 >= (q-1)*[2^(3-1)]+1 = 4q-3 > q.
      q is a proper factor, and n^2*k+1 is composite.
    - n+1 is a power of two: n=2^m-1 (m>0)
      Let k = m+2: 2^k = 4(n+1)
      Then n*2^k+1 = n*4(n+1)+1 = (2n+1)^2, composite.



    For all positive n, there is a k>0 such that n+2^k is composite.
    Cases:
    - n+1 is not a power of two, so has an odd prime factor q: n = mq-1
      Let k=q-1.
      Then n+2^k = (mq-1)+2^(q-1) == (mod q) -1+1 == 0.
      And n+2^k >= (q-1)+2^(3-1) = q+3 > q.
      q is a proper factor, and n+2*k is composite.
    - n+1 is a power of two: n=2^m-1 (m>0)
      --- m is odd: m=2r+1
          Let k=3.
          Then n+2^k = 2^(2r+1)-1 + 2^3 = 2*4^r + 7 == (mod 3) 2+7 == 0.
          And n+2^k >= 2^1-1 + 2^3 = 9 > 3.
          3 is a proper factor, and n+2^k is composite.
      --- m is even with odd proper factor q: m=qr
          Let k=1.
          Then n+2^k = 2^(qr)-1 + 2^1 = (2^r)^q+1,
          properly divisible by 2^r+1, so composite.
      --- m is an even power of two: m=2^x, n=2^(2^x)-1
          If x=0: 13 properly divides 2^(2^x)-1 + 2^6.
          If x=1: 13 properly divides 2^(2^x)-1 + 2^10.
          If x is even, x>0: 13 properly divides 2^(2^x)-1 + 2^7.
          If x is odd, x>1: 13 properly divides 2^(2^x)-1 + 2^9.

    For x=2,3,4,5,...: 2^(2^x) mod 13 = 3,9,3,9,... with period 2.
    Each is the square of the previous.

-- 
Don Reble  djr at nk.ca




More information about the SeqFan mailing list