A positive integer n is a semi-1 number if exactly half of the integers from 1 through n contain the digit 1. For example, 16 is semi-1, because exactly 8 of the integers between 1
and 16 contain the digit 1:
{1, 10, 11, 12, 13, 14, 15, 16}.
Find the largest semi-1 number you can find!
ones=0;nonOnes=0;
for n=1:10000000
ns=num2str(n);
if contains(ns,'1')
ones=ones+1;
else
nonOnes=nonOnes+1;
end
if ones==nonOnes
fprintf('%13s\n',(num2sepstr(n,'%8d')))
end
end
finds
2
16
24
160
270
272
1,456
3,398
3,418
3,420
3,422
13,120
44,686
118,096
674,934
1,062,880
Through 10,000,000, the stats are:
>> ones,nonOnes
ones =
5217032
nonOnes =
4782968
Adjusting these to 0 - 9,999,999:
ones =
5217031
nonOnes =
4782969
Then 10,000,000 - 19,999,999 all have 1's, so by the end of that span
ones =
15217031
nonOnes =
4782969
Each of the nine 10-million-number sets in the remaining 8-digit numbers have a surplus of 5217031 - 4782969 = 434062 numbers with a 1.
Going up to 100 million, there are no more semi-1 numbers, and since each 10 million has a surplus, we could have stopped at 20 million. No intervening imbalance in the opposite direction occurs between successive multiples of 10 million to temporarily balance out the ultimate excess.
That means that 1,062,880 is the absolute last semi-1 number.
|
|
Posted by Charlie
on 2024-03-13 08:34:52 |
computer exploration plus analytic limit
