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

Sat Jan 8 07:19:35 CET 2022

Dave, I have now checked the arguments in your message of Jan 2 pretty
carefully, and I believe your theorem 2b:

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.

  It is easy to see that for bases b > n/2, an even n has the single-digit
generator (n/2)_b.
So you looked at the range of bases where we must use two-digit generators,
and basically showed that a two-digit generator exists iff b+1 does not
divide (n+2)/2.

This cut down the search for "Universally generated numbers", A230624, to
searching for generators to the range of bases b <= sqrt(n). Very nice!

I took a look at the small even bases. Sequences A228082, A349831, A349832,
A349833 now list the even numbers that are generated in base 2, bases 2 and
4, bases 2,4,and 6, and bases 2,4,6, and 8, respectively.  It is a pity
that even the simplest of these, A228082 (or its complement, A010061,
Kaprekar's "self-numbers") doesn't have a simple formula. The sequence we
are trying to prove is infinite, A230624, is of course the limiting
intersection.

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 4:12 PM Neil Sloane <njasloane at gmail.com> wrote:

> 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/
>>>
>>