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

[Neil Sloane]

PS Dave, The first point in your argument is certainly well-known. See for
example Santanu Bandyopadhyay, <a href="
https://www.ese.iitb.ac.in/~santanu/RM8.pdf">Self-Number</a>, Indian
Institute of Technology Bombay (Mumbai, India, 2020). I added a link to it
to A230624.  I also added a link to one of the main sequences related to
this topic, A003052.


Best regards
Neil

Neil J. A. Sloane, Chairman, OEIS Foundation.
Also Visiting Scientist, Math. Dept., Rutgers University,
Email: njasloane at gmail.com



On Wed, Jan 5, 2022 at 3:55 PM Neil Sloane <njasloane at gmail.com> wrote:

> 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.
>
> Best regards
> Neil
>
> 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),
>> 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/
>>
>> --
>> Seqfan Mailing list - http://list.seqfan.eu/
>>
>