[seqfan] Re: Remeven numbers

[David Seal]

> A variant easier to consider could be
> 
>     "alleven" = integers where remainders modulo 1 to 9 are all even,
>                 and digit 0 not allowed
> 
> A state machine for that one is 79 states and its recurrence etc for how
> many digit strings of length k has biggest term 32/567 * 9^k.  But I
> have yet to triple check that ...
> ...
> Can this be had an easier way?  The absence of digit 0 seems to upset
> simple ways to think about remainders. ...

Well, there's an informal simple way to think about remainders that isn't rigorous, but does agree with that biggest term:

Remainder modulo 1 being even is of course trivially true. Remainder modulo 2 being even just means being even, and that's enough to ensure that the remainders modulo 4, 6 and 8 are all even. Remainder modulo 5 being even says that the number is 0, 2 or 4 modulo 5, and that combines with being even to say that the remainder modulo 10 is 0, 2 or 4. We can rule out the case of remainder 0 modulo 10 because that implies that the least significant digit is 0.

So we can conclude that the remainder modulo 10 is in {2,4}, and we still have to deal with the remainders modulo 3, 7 and 9. The remainders modulo 3 and 9 both being even implies that the remainder modulo 9 is in {0,2,6,8}, and the remainder modulo 7 being even implies that it is in {0,2,4,6}. Since 7, 9 and 10 are coprime, each of the 4*4*2=32 combinations of those remainders is satisfied by one remainder modulo 7*9*10=630 - i.e. 32 out of every 630 integers have even remainders modulo each of 1 to 9.

There are 9 * 10^(k-1) integers of length k digits, so we expect the number of those integers that have even remainders modulo each of 1 to 9 to be about (32/630) * 9 * 10^(k-1). We know that the digits at each end of those numbers are nonzero, and on the assumption that each of the k-2 non-end digits behaves pretty randomly and can be expected to be 0 a tenth of the time (the most non-rigorous part of this argument!), a fraction (9/10)^(k-2) of them can be expected to contain no 0s. That makes number of k-digit alleven numbers about (32/630) * 9^(k-1) * 10 = (32/567) * 9^k.

> Trying that ratio on some actual counts, alleven approaches 32/567 quite
> quickly, but remeven is disconcertingly slow.  Perhaps that's to be
> expected if you're waiting for a term in 9^k to squash terms in 8^k.

The remeven condition tests fewer moduli than the alleven condition for all <=8-digit numbers, so the remeven condition is more relaxed than the alleven condition until you get up to 10^8. And even after you get to 10^8, only 9! of the 9^9 9-digit non-0-containing numbers, which is only about 0.09% of them, and the proportion doesn't grow all that quickly as the number of digits increases. To get at least 50% of the k-digit non-0-containing numbers to contain all of 1 to 9, k must be at least 23, and to get at least 90% of them to do so, k must be at least 38. In that context, it hardly seems surprising that the remeven density approaches the alleven density very slowly...

Though in fact, it isn't necessary for a number to contain all of the digits 1 to 9 to make the remeven condition as strict as the alleven condition, because (a) it doesn't need to contain a digit 1, since the remainder modulo 1 is always even; (b) it just needs to contain one of the even digits since the remainder modulo any one of them being even implies that the number is even, which implies that the remainder modulo all of them is even. So once a number contains an even digit, a 3, a 5, a 7 and a 9, the remeven test is as stringent as the alleven test.

So one only needs to get up to 5-digit numbers to have some chance that the remeven condition is as stringent as the alleven condition. But a calculation involving counting the numbers of integers that use the 32 subsets of {even,3,5,7,9} says that there's only about a 0.81% chance for 5 digits, and one needs 17 digits to grow to more than 50% and 32 digits to grow to more than 90%. So I would still expect the remeven density to approach the alleven density quite slowly.

David


> On 10 January 2020 at 05:53 Kevin Ryde via SeqFan <seqfan at list.seqfan.eu> wrote:
> 
> 
> oeis at hasler.fr (M. F. Hasler) writes:
> >
> > oeis.org/A330981 and oeis.org/A330982.
> 
> A variant easier to consider could be
> 
>     "alleven" = integers where remainders modulo 1 to 9 are all even,
>                 and digit 0 not allowed
> 
> A state machine for that one is 79 states and its recurrence etc for how
> many digit strings of length k has biggest term 32/567 * 9^k.  But I
> have yet to triple check that ...
> 
> Alleven is a subset of remeven.  Extras in remeven are when fewer than
> all digits 1 to 9 occur, so at most 8 different digits, so at most 9*8^k
> extras, which is smaller than power 9^k, so should have same limit
> 32/567 * 9^k remeven digit strings of length k.
> 
> For how many <= any integer n, I tried counting alleven where the start
> state is something different.  This is some initial digit string
> followed by k more digits.  Looks like limits 32/567 * 9^k no matter
> what initial digits.  I think I'm persuaded this ought to mean
> 
>                    num remeven <= n
>      lim    ---------------------------------   = 32/567
>     n->inf  num integers without 0 digit <= n
>                    (A052382, A324161)
> 
> Trying that ratio on some actual counts, alleven approaches 32/567 quite
> quickly, but remeven is disconcertingly slow.  Perhaps that's to be
> expected if you're waiting for a term in 9^k to squash terms in 8^k.
> 
> Can this be had an easier way?  The absence of digit 0 seems to upset
> simple ways to think about remainders.  Oh, and I don't like my name
> "alleven" so something better :).
> 
> 
> In general, is there a name for a regular language where the number of
> strings with a particular prefix has the same limit as number of all
> strings?  I think I mean for any given fixed string "prefix"
> 
>              num strings <prefix>.<length k>
>      lim     -------------------------------  = 1
>     k->inf        num strings <length k>
> 
> --
> Seqfan Mailing list - http://list.seqfan.eu/