Proposed seq: Smallest prime with exactly 2n+1 ones when written in base 3

Jonathan Post jvospost3 at gmail.com
Wed Jul 2 07:17:04 CEST 2008

```In seeking a base 3 analogue of:

Cf.  A061712  Smallest prime with Hamming weight n (i.e.
with exactly n 1's when written in binary).

we can't, after 2 (base 10) = 2 (base 3) have a prime with an even
number of 1's in base 3, because 3^a + 3^b is even.  So the closest
analogue is:

n  a(n) = Smallest prime with exactly 2n+1 ones when written in base 3
0  3 = 10 (base 3) which has 2*0+1 ones
1  13 = 111 (base 3) which has 2*1+1 ones
2  283 = 101111  (base 3) which has 2*2+1 ones
3  1093 = 1111111 (base 3) which has 2*3+1 ones

It is heuristically plausible that this sequence is well-defined.
Does every a(n) have no digit 2?

This seq was suggested by Dr. George Hockney

Cf. A007089, A066195  Smallest prime containing n zeros in its binary expansion,

jvp> From seqfan-owner at ext.jussieu.fr  Wed Jul  2 07:18:08 2008
jvp> Date: Tue, 1 Jul 2008 22:17:04 -0700
jvp> From: "Jonathan Post" <jvospost3 at gmail.com>
jvp> To: SeqFan <seqfan at ext.jussieu.fr>,
jvp>         "Dr. George Hockney" <george.hockney at jpl.nasa.gov>
jvp> Subject: Proposed seq: Smallest prime with exactly 2n+1 ones when written in base 3
jvp>
jvp> In seeking a base 3 analogue of:
jvp>
jvp> Cf.  A061712  Smallest prime with Hamming weight n (i.e.
jvp> with exactly n 1's when written in binary).
jvp>
jvp> we can't, after 2 (base 10) = 2 (base 3) have a prime with an even
jvp> number of 1's in base 3, because 3^a + 3^b is even.  So the closest
jvp> analogue is:
jvp>
jvp> n  a(n) = Smallest prime with exactly 2n+1 ones when written in base 3
jvp> 0  3 = 10 (base 3) which has 2*0+1 ones
jvp> 1  13 = 111 (base 3) which has 2*1+1 ones
jvp> 2  283 = 101111  (base 3) which has 2*2+1 ones
jvp> 3  1093 = 1111111 (base 3) which has 2*3+1 ones

Adding a few more terms we get
3,13,283,1093,22963,259159,797161,19929037,150663523

And because the smallest number with n ones in base 3 is
3^0+3^1+3^2+...+3^(n-1)=(3^n-1)/2=A003462(n), we have a lower bound

a(n) >= A003462(2n+1) = A096053(n).

Definition could be rephrased as:

a(n) := {min A000040(i): A073780(i)=2n+1}.

jvp>
jvp> It is heuristically plausible that this sequence is well-defined.
jvp> Does every a(n) have no digit 2?
jvp>
jvp> This seq was suggested by Dr. George Hockney
jvp>
jvp> Cf. A007089, A066195  Smallest prime containing n zeros in its binary expansion,

We also have "smallest prime with exactly n ones in base 4"
7,5,89,277,1109,5477,17749,70997,349529,

"smallest prime with exactly n ones in base 5":
5,41,31,1031,3881,19541,19531

"smallest prime with exactly n ones in base 6":
11,7,43,1549,9337,56131,55987

"smallest base in which the n-th prime has 2 ones and zeros elsewhere"
I guess this is A006093(n).

These are all biased in even two ways: first there is the dependence on the
base, and second there is no reason to count the number of ones (as opposed to
2's, 3's,..).

And there is some (not interesting IMO) auxiliary array of T(i,b) of
the number of ones of the i-th prime, i=1,2,3,.. in base b=2,3,4,...

1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
2,1,2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
3,1,1,1,2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,
3,1,0,1,1,1,1,1,2,1,0,0,0,0,0,0,0,0,0,
3,3,1,0,1,1,1,1,1,1,2,1,0,0,0,0,0,0,0,
2,1,2,0,0,0,1,1,1,1,1,1,1,1,2,1,0,0,0,
3,1,1,0,1,0,0,1,1,1,1,1,1,1,1,1,2,1,0,
4,1,2,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,
4,1,2,1,0,1,0,0,0,0,0,0,1,1,1,1,1,1,1,
5,3,1,3,1,0,0,0,1,0,0,0,0,1,1,1,1,1,1,
3,3,2,1,2,0,0,1,0,0,1,0,0,0,0,0,1,1,1,
3,3,1,2,1,0,1,0,1,0,0,0,0,0,0,0,0,0,1,
4,3,0,1,3,1,0,0,0,0,0,0,1,0,0,0,0,0,0,
5,1,0,1,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
4,1,2,0,1,1,0,0,0,0,0,1,0,0,0,0,0,0,0,
5,1,0,1,1,2,0,0,0,0,0,0,0,0,0,0,0,0,0,
5,1,1,1,2,2,0,0,1,0,1,0,0,1,0,0,0,0,1,
3,3,1,0,2,1,1,0,0,1,0,0,0,0,0,0,0,0,0,
4,1,2,1,1,2,1,0,1,0,0,0,1,0,0,0,0,0,0,

which contains A014499 in the first column, A073780 in the 2nd column.

Richard

```