[seqfan] Re: Numbers that are "generated" in every base
njasloane at gmail.com
Wed Jan 5 21:55:52 CET 2022
I was waiting to hear the results of your computation, but I see you've
already uploaded a new b-file. So I assume your worries about possible
gaps in the proof have gone away. Could you upload a worry-free version of
your proof to A230624, to go along with the b-file? It could simply be a
.txt file based on your email.
Neil J. A. Sloane, Chairman, OEIS Foundation.
Also Visiting Scientist, Math. Dept., Rutgers University,
Email: njasloane at gmail.com
On Sun, Jan 2, 2022 at 4:04 PM David Applegate <david at bcda.us> wrote:
> A couple of comments about A230624 (some probably already known, but not
> explicitly mentioned in the email or sequence comments, and I didn't
> notice them in a quick glance at the linked paper:
> 1. If b is odd, then n is generated by k in base b iff n is even. Hence
> we don't need to consider odd b or odd n.
> 2a. (as mentioned in the email) If n is even, then n is generated by
> k=n/2 in every base b > n/2.
> 2b. Claim: If n is even, let 2^i be the largest power of 2 dividing
> n+2. If (n+2)/2^i - 1 > sqrt(n), then there is no k such that n is
> generated by k in base b=(n+2)/2^i - 1 > sqrt(n). Otherwise n is
> generated by some k in every base b with sqrt(n) <= b <= n/2.
> Proof sketch:
> If n is even, b is even, and 2b <= n < b^2 + 1 and n is generated by k
> in base b, then k must have exactly 2 digits. Set x = 2*floor(n /
> (2b+2)), y=mod(n, 2b+2)/2. Then x < b, and if 2b+2 does not divide n+2,
> y < b. In that case, x is generated by k=x*b+y in base b (k + S_b(k) =
> (x*b + y) + (x + y) = x*(b+1) + 2y = (2b+2)*floor(n / (2b+2)) + mod(n,
> 2b+2) = n).
> Thus, for sqrt(n) <= b <= n/2, the bases b without generators are
> exactly the even b where b+1 divides (n+2)/2. Since b+1 is odd, we can
> let 2^i be the largest power of 2 that divides (n+2), and write (b+1) (j
> 2^i) = n+2, or b = (n+2) / (j 2^i) - 1, for j odd. But if j=1 gives a b
> >= sqrt(n), there is no generator. If j=1 gives a b < sqrt(n), then
> all larger j will also give b < sqrt(n). So it suffices to consider j=1.
> Possible gaps:
> I might have gotten a < vs <= mixed up, or an off-by-one error to make
> sure that for the examples cited, 1-digit and 3-digit k are excluded.
> Also, it is possible I overlooked something in the possible 2-digit
> solutions. Or, there's something more fundamental wrong.
> Given that claim, n is in A230624 iff:
> 1. n is even,
> 2. n has a generator for each base b <= sqrt(n), and
> 3. (n+2) / 2^i - 1 <= sqrt(n) (where 2^i is the largest power of 2
> dividing n+2).
> I'm generating a b-file containing entries <= 10^9 based on this claim,
> and will upload it once it's done (it's currently up to 0.8 * 10^9).
> On 12/31/2021 11:25 PM, Neil Sloane wrote:
> > Dear Sequence Fans,
> > Kaprekar says that n is "generated by k in base b" if n = k + S_b(k),
> > S_b(k) is the sum of the digits of k when k is written in base b. For
> > example in base 10, 101 has two generators, 91 and 100. 101 is the
> > number with two generators in base 10. For more background see the paper
> > that Max Alekseyev and I just finished:
> > http://neilsloane.com/doc/colombian12302021.pdf (it is also on the arXiv
> > but this version is better). A "self-number in base b" has no generator.
> > All numbers here are nonnegative, by the way.
> > What I am writing about is A230624, the list of numbers that have a
> > generator in every base b >= 2. There are 90 known terms (the b-file is
> > from Lars Blomberg). It begins 0, 2, 10, 14, 22, 38, 62, 94, ... It seems
> > it is not known whether this sequence is infinite. This seems like a very
> > nice problem, if anyone is interested. I created subsidiary sequences
> > A349820 - A349823, hoping some structure would emerge, without much
> > By the way, it is easy to see that all terms must be even, and if the
> > number is n = 2t, once b is greater than t, n is generated by the base-b
> > single-digit number t. So we only need to find generators for bases 2
> > through n/2. See A349223 for certificates for the first few terms of
> > A230624.
> > --
> > Seqfan Mailing list - http://list.seqfan.eu/
> Seqfan Mailing list - http://list.seqfan.eu/
More information about the SeqFan