a(n) = Smallest Multiple Of a(n-1) With Exactly n Binary 1's

[Jack Brennen]

Leroy Quet wrote:
> Let a(1) = 1. Let a(n) = the smallest positive multiple of a(n-1) with exactly n 1's in its binary representation.
> 
> The sequence begins (though, I could be wrong, of course): 1,3,21,105,...
> 

It continues ...,4305,21525,5316675,3291021825,...


The next term is > 2^59, but less than or equal to
    295167045907433652225.






> From seqfan-owner at ext.jussieu.fr  Sat Jul  5 00:08:45 2008
> Date: Sat, 05 Jul 2008 00:07:04 +0430
> From: Artur <grafix at csl.pl>
> Reply-To: grafix at csl.pl
> To: Richard Mathar <mathar at strw.leidenuniv.nl>
> CC: seqfan at ext.jussieu.fr
> Subject: Re: Q: prime number congruences and quadratic forms: A141778=A038977?
> 
> Also
> A141158 <http://www.research.att.com/%7Enjas/sequences/A141158>=A141130
> <http://www.research.att.com/%7Enjas/sequences/A141130>=A038872
> <http://www.research.att.com/%7Enjas/sequences/A038872>
> A141131 <http://www.research.att.com/%7Enjas/sequences/A141131>=A038873
> <http://www.research.att.com/%7Enjas/sequences/A038873>=A049594
> <http://www.research.att.com/%7Enjas/sequences/A049594>=A049590
> <http://www.research.att.com/%7Enjas/sequences/A049590> (titles
> different sequences that same)
> A141186 <http://www.research.att.com/%7Enjas/sequences/A141186>=A141122
> <http://www.research.att.com/%7Enjas/sequences/A141122>=A068228
> <http://www.research.att.com/%7Enjas/sequences/A068228>
> A141123? <http://www.research.att.com/%7Enjas/sequences/A141123>=A141187
> <http://www.research.att.com/%7Enjas/sequences/A141187>
> A141132 <http://www.research.att.com/%7Enjas/sequences/A141132>=A141188
> <http://www.research.att.com/%7Enjas/sequences/A141188>=A038883
> <http://www.research.att.com/%7Enjas/sequences/A038883>
> A141133 <http://www.research.att.com/%7Enjas/sequences/A141133>=A038889
> <http://www.research.att.com/%7Enjas/sequences/A038889>
> A141130 <http://www.research.att.com/%7Enjas/sequences/A141130>=A038872
> <http://www.research.att.com/%7Enjas/sequences/A038872>=A141158 also
> <http://www.research.att.com/%7Enjas/sequences/A141158>A123976 differ
> only a(1) <http://www.research.att.com/%7Enjas/sequences/A123976>
> A141159 <http://www.research.att.com/%7Enjas/sequences/A141159> also
> title that same as A139492
> <http://www.research.att.com/%7Enjas/sequences/A139492>
> A141170 <http://www.research.att.com/%7Enjas/sequences/A141170>=A106950
> <http://www.research.att.com/%7Enjas/sequences/A106950>
> A141172 <http://www.research.att.com/%7Enjas/sequences/A141172>?=A107134
> <http://www.research.att.com/%7Enjas/sequences/A107134>
> A141174 <http://www.research.att.com/%7Enjas/sequences/A141174>=A007519
> <http://www.research.att.com/%7Enjas/sequences/A007519>
> A141175 <http://www.research.att.com/%7Enjas/sequences/A141175>=A007522
> <http://www.research.att.com/%7Enjas/sequences/A007522>
> A141177 <http://www.research.att.com/%7Enjas/sequences/A141177>?=A107013
> <http://www.research.att.com/%7Enjas/sequences/A107013>
> A141178 <http://www.research.att.com/%7Enjas/sequences/A141178>=A038913
> <http://www.research.att.com/%7Enjas/sequences/A038913>
> Best wishes
> Artur

Since I have not seen a proof of equivalence of these
forms which represent primes. In overview, we have the following OEIS numbers,
coefficient 'a' in the quadratic form Q: p=ax^2+bxy+cy^2, discriminant D=b^2-4ac,
and Legendre symbol (4a/D):

Q       a   D     D mod 4   (4a/D) qRes
A141130 1   5     1          +1    A038872
A141132 1   13    1          +1    A038883
A141133 2   17    1          +1    A038889
A141178 3   37    1          +1    A038913
A141181 2   41    1          +1    A038919
A141189 1   53    1          +1    A038931
A141215 3   61    1          +1    A038941
A141750 4   73    1          +1    A038957
A141778 4   89    1          +1    A038977

Generally we can diagonalize the quadratic form by introducing z=2ax+by
as a new integer ("completing the square") such that it is equivalent
to  4ap=z^2 -D y^2. Working modulo the discriminant D we get the
residue mod D, or that the Legendre symbol (4ap/D)=+1 for the primes
in these sequences. Using the "class multiplication" formula for the Legendre
have (p/D)=+1. Since all the D are 1 (mod 4), the law of quadratic reciprocity
concludes that also (D/p)=+1, which we rephrase "D is a quadratic residue mod p"
(The case p=D is to be considered separately.)

So far this proves that the sequences A141xxx at the left of the table in
the Q column are subsets of the sequences A038xxx on the same lines in the qRes
column to the right.

For the reduction in the opposite direction, one needs to answer the
question whether 4ap = z^2-Dy^2 (a Pell's equation) is always solvable with integers
z and y given D and a and the primes p in the A038xxx sequence.
chapter 19 of Mordell's "Diophantine equations" (1969). This means that 4ap=z^2-Dy^2
are solvable for a=1 by doubling z and y [ensuring that x=(z-by)/(2a) is integer].
To deduce that 8p=z^2-Dy^2 with D=17 is solvable, we note that 8=z^2-Dy^2 is
follow by building the products (see eq (5) in Mordell's book).

In summary we showed that
A141130 is a duplicate of A038872
A141132 is a duplicate of A038883
A141133 is a duplicate of A038889
A141178 is a subsequence of  A038913
A141181 is a subsequence of  A038919
A141189 is a subsequence of  A038931
A141215 is a subsequence of  A038941
A141750 is a subsequence of  A038957
A141778 is a subsequence of  A038977

The question whether A038913 is a subsequence of A141178 etc is left
undecided (so the question of duplicity remains open for these 6 cases).

Richard, www.strw.leidenuniv.nl/~mathar