mersenneforum.org An unreasonable operation
 Register FAQ Search Today's Posts Mark Forums Read

 2020-02-09, 19:54 #1 fivemack (loop (#_fork))     Feb 2006 Cambridge, England 11001000101112 Posts An unreasonable operation 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.
 2020-02-09, 20:20 #2 Boltzmann brain   Feb 2020 138 Posts 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).
 2020-02-09, 20:21 #3 fivemack (loop (#_fork))     Feb 2006 Cambridge, England 3·2,141 Posts 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 Last fiddled with by fivemack on 2020-02-09 at 20:22
2020-02-10, 03:00   #4
CRGreathouse

Aug 2006

175B16 Posts

Quote:
 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.

Quote:
 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:

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.

2020-02-10, 14:41   #5
Dr Sardonicus

Feb 2017
Nowhere

2·2,333 Posts

Quote:
 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!

Quote:
 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.

Quote:
 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, ...,bN*k, if N is "large enough" (this depends on b). But this determination is heavy-handed, to say the least.

2020-02-10, 15:41   #6
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

2×743 Posts

Quote:
 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.

2020-02-10, 20:53   #7
Dr Sardonicus

Feb 2017
Nowhere

2·2,333 Posts

Quote:
 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post clowns789 Operation Billion Digits 574 2017-09-12 01:34 Oddball Twin Prime Search 370 2013-01-03 21:26 smslca Math 3 2011-04-18 17:18 hashim kareem Operation Billion Digits 1 2005-03-05 13:51 eepiccolo Math 7 2003-01-08 03:07

All times are UTC. The time now is 04:10.

Sun Aug 1 04:10:11 UTC 2021 up 8 days, 22:39, 0 users, load averages: 2.20, 2.30, 1.87