mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2020-02-09, 19:54   #1
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

11001000101112 Posts
Default 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.
fivemack is offline   Reply With Quote
Old 2020-02-09, 20:20   #2
Boltzmann brain
 
Feb 2020

138 Posts
Default

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).
Boltzmann brain is offline   Reply With Quote
Old 2020-02-09, 20:21   #3
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

3·2,141 Posts
Default

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
fivemack is offline   Reply With Quote
Old 2020-02-10, 03:00   #4
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

175B16 Posts
Default

Quote:
Originally Posted by fivemack View Post
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 View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2020-02-10, 14:41   #5
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

2·2,333 Posts
Default

Quote:
Originally Posted by fivemack View Post
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.
Dr Sardonicus is offline   Reply With Quote
Old 2020-02-10, 15:41   #6
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

2×743 Posts
Default

Quote:
Originally Posted by fivemack View Post
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.
R. Gerbicz is offline   Reply With Quote
Old 2020-02-10, 20:53   #7
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

2·2,333 Posts
Default

Quote:
Originally Posted by fivemack View Post
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.
Dr Sardonicus is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Operation: Billion Digits clowns789 Operation Billion Digits 574 2017-09-12 01:34
Operation Megabit Twin Oddball Twin Prime Search 370 2013-01-03 21:26
modulo operation for polynomials? smslca Math 3 2011-04-18 17:18
implimentation of large integer operation hashim kareem Operation Billion Digits 1 2005-03-05 13:51
The modulo operation, how is it computed? 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.