Numbers with disjoint binary and decimal suffixes

[David Radcliffe]

Greetings!

If n ≥ 0 and b ≥ 2 are integers, define S(n, b) = {n mod b^k | b^k < n}. This is the set of proper suffixes of n in base b. For example, S(1024, 10) = {4, 24}.

Say that a number n is "good" if the sets S(n, 10) and S(n, 2) are disjoint. How many numbers are good?

Empirically, the number of good numbers less than 10^n is 10*(4^n - 1)/3 + 0^n (sequence A086462), but I have no idea why this might be true. I have verified it up to n=8. (The 0^n term is based on the convention that 0^0 = 1.)

Can you enlighten me?

[Neil Sloane]

"define S(n, b) = {n mod b^k | b^k < n}".   Perhaps k needs to be restricted?  Would 

"{n mod b^k | there exists a positive integer k such that b^k < n}" be closer to what you want?

Best regards

Neil 

Neil J. A. Sloane, Chairman, OEIS Foundation.

Also Visiting Scientist, Math. Dept., Rutgers University, 

Email: njas...@gmail.com

--
You received this message because you are subscribed to the Google Groups "SeqFan" group.
To unsubscribe from this group and stop receiving emails from it, send an email to seqfan+un...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/seqfan/CAJ7c8Cn6Cz7F7bFALFokB-QoLxL5fGBD1-PhqCTHzjF1TbYZBw%40mail.gmail.com.

[David Radcliffe]

Yes, that is more accurate.

Define S(n, b) = {n mod b^k | there exists a positive integer such that b^k < n},

and let a(n) = # { m in {0, 1, 2, ...,  10^n - 1} | S(m, 10) and S(m, 2) have empty intersection}.

Does a(n) = 4*a(n-1) + 10 for n >= 1?

I have verified this up to n=9, but it could be the law of small numbers.

To view this discussion visit https://groups.google.com/d/msgid/seqfan/CAAOnSgSDdbMZMWdywwCCYkFBshWRGeg2NERAJv-jwYFOKntgLg%40mail.gmail.com.

[Gareth McCaughan]

My idiotic Python code says that there are 64 good nonnegative integers
< 100, versus the 51 given by your formula: 1, 2, 3, 4, 5, 6, 7, 8, 9,
12, 13, 14, 15, 16, 17, 18, 19, 24, 25, 26, 27, 28, 29, 32, 33, 34, 35,
36, 37, 38, 39, 48, 49, 52, 53, 54, 55, 56, 57, 58, 59, 64, 65, 66, 67,
68, 69, 72, 73, 74, 75, 76, 77, 78, 79, 92, 93, 94, 95, 96, 97, 98, 99.

The two-digit number [ab] is good iff b isn't a proper suffix of [ab] in
base 2. In general m is a proper suffix of n in base b iff n-m is a
nonzero multiple of a power of b bigger than m, so here what we need to
avoid is for 10a to be a multiple of a power of 2 bigger than b, or
equivalently for a to be a multiple of a power of 2 bigger than b/2. For
a=1,3,5,7,9 this means that b/2<1 or b<2: 10 possibilities here. For
a=2,6 this means that b/2<2 or b<4: 8 possibilities here. For a=4 this
means that b<8: 8 possibilities again. For a=8 it means b<16: 10
possibilities. And for a=0 that "nonzero" condition means that no b will
do: 0 possibilities. So the number of bad <=2-digit numbers should be
10+8+8+10=36 leaving 64 good numbers.

What am I missing?

My idiotic Python code thinks the sequence begins 1, 10, 64, 566, 5370,
53026, 527206.

In general, if you have the base-10 number [AB] where now A,B are
arbitrary sequences of digits, B is a base-2 proper suffix if
10^len(B).A is a nonzero multiple of a power of 2 bigger than B, which
is the same as A being a nonzero multiple of a power of 2 bigger than
B/2^len(B), which is the same as B < 2^(n2(A)+len(B)) where n2(A) means
number of factors of 2 dividing A. So for given A the number of such B
of length k is min(10^k,2^(n2(A)+k)) and the number of A of length m
with n2(A)=r is floor(10^m/2^r)-floor(10^m/2^(r+1)), so the number of
things bad _in this particular way_ with len(A)=m and len(B)=k is the
sum over r of [floor(10^m/2^r) - floor(10^m/2^(r+1))] min(10^k,2^(r+k)).
Of course this doesn't solve the problem because we need to account for
the possibility that a number can be bad in multiple ways, which seems
kinda painful. Also, I've slightly fudged the issue of leading zeros;
the above allows A to have leading zeros but not itself to be zero.

(Taking m=2,k=1 -- this corresponds to looking at numbers from 10 to 999
and considering only badness on account of the length-1 suffix in base
10 -- this gives 416 bad numbers, and hence 990-416=576 good numbers, in
this range, hence 586 good numbers below 1000. The actual number is 566.
The number of numbers from 100 to 999 that are bad on account of the
length-2 suffix in base 10 is 84, so there is indeed quite a lot of
double-counting. All of the above assumes that my code doesn't consist
entirely of bugs, which on past experience is not a very safe assumption.)

--
g

[David Radcliffe]

My script had a careless mistake. My apologies for cluttering the mailing list.