[seqfan] Re: Numbers that are "generated" in every base

[David Applegate]

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), where
> 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 smallest
> 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 success.
>
>
> 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/