An unreasonable operation

[fivemack]

Consider the operation where you double a number and then cross out all the zeroes in its base-10 representation

eg 34 -> 68 -> 136 -> 272 -> 544 -> 188 -> 376 -> 752 -> 154 -> 38 -> 76 -> 152 -> 34

It's heuristically obvious that every number ends up in a cycle. Running on starts up to 10^6 and 3141592653589 .. 3141592753589 gives me a reasonably strong belief that the shortest cycle length is 12 and the longest 432 (starting 118), which is more structure than I'd have expected.

You get the same sort of various-limit-cycles behaviour for multiplying by K rather than doubling; K=6 has fixed points (eg 18). K=7 has a much larger set of limit cycles, ranging from a fixed point at 15 to a cycle of length 6600 starting with 1157313. k=8 also gives quite a wilderness of limit cycles.

By k=11 there is a cycle of length 30960 (hit by 925, where the first repeated value is 786699925).

I don't have a clue how to prove that there aren't other cycles.

[Boltzmann brain]

The likelihood of a random number containing a 0 increases as the size of the integer increases, so there will be a certain range of values at which numbers no longer increase on average. This is the range where the loops will be. I think you can conclude above a certain value that such things are unlikely, but attempting to prove that no more cycles exist seems similar to trying to prove the collatz conjecture. I happen to have posted a sequence in the "math" forum recently that is a similar kind of operation, though it doesn't have a dependence on its size (meaning the numbers can get extremely large if a sequence meanders in that direction).

[fivemack]

An analogous question:

Prove there is no integer for which n, 2n, 4n, ..., (2^20)n all have no 0 in their decimal expansion

Find an integer for which n, 2n, 4n, ..., (2^19)n all have no 0 in their decimal expansion


Much harder if you look at powers of 3, 7 or 9

[CRGreathouse]

Originally Posted by fivemack

Prove there is no integer for which n, 2n, 4n, ..., (2^20)n all have no 0 in their decimal expansion

Nicely done.

Originally Posted by fivemack

Find an integer for which n, 2n, 4n, ..., (2^19)n all have no 0 in their decimal expansion

I believe 348612479 will do. My search code:

has(n)=vecmin(digits(n))>0
is(n)=for(k=1,19,if(!has(n<<k),return(0)));1
for(N=1,9^8, n=fromdigits(digits(N,9)); k=n%10; if((k==2||k==7) && is(10*n+9), return(10*n+9)))

No doubt this could have been done more efficiently.

[Dr Sardonicus]

Originally Posted by fivemack

An analogous question:

Prove there is no integer for which n, 2n, 4n, ..., (2^20)n all have no 0 in their decimal expansion

Very nice!

Find an integer for which n, 2n, 4n, ..., (2^19)n all have no 0 in their decimal expansion

Pass. I do know something nontrivial about such n, but finding one looks like a slog.

Much harder if you look at powers of 3, 7 or 9

As long as b is not a power of ten, there is a line of reasoning indicating that, if k is a positive integer, there is a fixed value of N for which a 0 will always show up among the decimal expansions of the multiples k, b*k, ...,b^N*k, if N is "large enough" (this depends on b). But this determination is heavy-handed, to say the least.

[R. Gerbicz]

Originally Posted by fivemack

Consider the operation where you double a number and then cross out all the zeroes in its base-10 representation

eg 34 -> 68 -> 136 -> 272 -> 544 -> 188 -> 376 -> 752 -> 154 -> 38 -> 76 -> 152 -> 34

It's heuristically obvious that every number ends up in a cycle. Running on starts up to 10^6 and 3141592653589 .. 3141592753589 gives me a reasonably strong belief that the shortest cycle length is 12 and the longest 432 (starting 118), which is more structure than I'd have expected.

Found only one cycle with start number>1e6, that is n=3958368 with cycle length=16.
It is easy to see that the length should be divisible by four, and n mod 10 is in {2,4,6,8}.

And if we'd delete 1 in the numbers (instead of zero), then for every starting number it goes to a cycle, because the iterated numbers can't be longer, otherwise (2*n) would be start by one, but we delete that.

[Dr Sardonicus]

Originally Posted by fivemack

Find an integer for which n, 2n, 4n, ..., (2^19)n all have no 0 in their decimal expansion

I decided to look for smaller solutions than the one already posted. 17929 fills the bill.