Problems & Puzzles: Puzzles

 Puzzle 644. 123 Curio Recently  I found a nice toy to play with. It's a recursive rule to apply to any integer. The curio thing is that no matter what is your initial integer choice, you will terminate always in the integer 123.The only & recursive rule is this one: Given any integer N1 construct a new integer N2= E&O&T, where E is the count of even digits in N1; O is the count of odd digits in N1 & T=E+O. Example: Let N1=2147483647 (the beautiful Mersenne prime discovered by Euler in 1772) N1 = 2147483647 -> 6410 -> 314 -> 123 (K steps to reach 123 from N1 = 3) After playing a while with this curio I started asking myself for the smallest integer that needs K steps to reach 123 The smallest prime for K=3 is not 2147483647 but the much smaller 1021. Then I managed to imagine, construct & verify  the smallest integer and the smallest prime for K=4 (quite larger than 2147483647 ) and... then I decided to post this puzzle because I failed even to imagine the smallest solutions for K=5 Q1. Can you explain why applying this rule you always end in 123? Q2. Can you rediscover the smallest integer and the smallest prime for K=4? Q3. Can you indicate what is the smallest integer for K=5?

1) I missed to explain that I was accepting leading zeros from the first step on.
2) I made a mistake when I wrote that for K=3, the smallest prime was 1021; it should have been 1009.

E&O&T means the concatenations of E, O and T.

Sorry folks!

***

Contributions came from Giovanni Resta, Fred Schalekamp, Gaurav Kumar, Emmanuel Vantieghem, Antoine Verroken and Farideh & Jahangeer

***

Giovanni wrote:

it seems to me that some very small numbers need 5 iterations.
For example, starting from 1 (0 even digits, 1 even digit, 1 total digits) I obtain 011 = 11 and along this line I have:

1 -> 11 -> 22 -> 202 -> 303 -> 123

Analogously, the smallest prime that needs 3 iterations seems to
be 1009, not 1021.

1009 -> 224 -> 303 -> 123

Maybe there is something I'm missing.

***

Fred wrote:

I'm doing something wrong.

1=>11=>22=>202=>303=>123

It seems too easy.....

***

Gaurav wrote:

Why is 1009 not the smallest prime for K = 3?

1009 -> 224-> 303 -> 123

***

Emmanuel wrote:

Q1. This is easy.  Simply prove it for all numbers with, say, four digits 'by hand' (by PC is also allowed)  and prove the general statement by induction : every five- or more-digit number is transformed by the rule in a number with fewer digits...

Q2.  K = 1.  Smallest number = 101 = Smallest prime

K = 2.  Smallest number = 2 = Smallest prime

K = 3.  Smallest number = 20 ; smallest prime = 1009 (and not 1021)

K = 4.  Smallest number = 11 = smallest prime

Q3.  K = 5.  Smallest number = 1 ; Smallest prime = 3

Indeed, define the function  F  by  the rule  F(m) = E&O&T.

The chain obtained by the itteration of  F  is then :

3 -> 11 -> 22 -> 202 -> 303 -> 123

However, I think that the really tough problem is to find a chain of length 6 (or longer).

Here is how I constructed a chain of infinite length :

... -> X(n+1) -> X(n) -> ... -> X(2) -> X(1) -> 123

with  X(1)  = 145,  X(2) = 11011,  X(3) = 11111011111,

X(4)  is a number with  11111  digits, all ones except the middlest which is zero.

Thus, X(4)  is of the form

A&0&A

where  A  is the repunit consisting of  5555  ones.

Further, X(5)  will be of the form

B&0&B

where  B  is the repunit consisting of  (A-1)/2  ones.

Further, X(6)  will be of the form

C&0&C

where  C  is the repunit consisting of  (B-1)/2  ones, etcetera.

In that way we can extend the chain to the left ad infinitum !

If we ask for the smallest number  m  with  K = 6, we must replace  X(6)  by the smaller number obtained by moving the middlest 0 to the second position from the left.  Thus, m will be of the form   1011...11 = 1&0&M, where  M  is the repunit with  2C-1  ones.  Since  F(m)  is obviously the same as  F(X(6)), the chains

m -> F(m) -> F(F(m)) -> ...

ends with the same tail.

However, I cannot prove that  m  is effectively the smallest possible.

But that number is tremendously big so that perhaps no one can have an idea what will be the smallest prime ...

***

Antoine wrote:

Q1 :

1.       Applying several times the ‘ rule ‘ we get a 3 digit number.

2.       with “ e = even  z =zero = e   o = odd   n = e + o “ the different possibilities for

that 3 digit number are :

e o n                e e n                o o n

or   e o o                e e e                o o e

or   1 2 3                3 z 3                1 2 3

1 2 3

***

Farideh & Janeeger wrote:

 a)  If n has only one digit then we have two following cases:   1. n is odd:  n --> 11 -->  22 --> 202 --> 301 --> 123    k = 5 2. n is even: n --> 101 -->  123                                  k = 2   b)  If n has two digits then we have four following cases:   1. n has two even digits  :  n --> 202 --> 303 --> 123          k = 2 2. n has only one even digits  :  n --> 213 --> 123    k = 2 3. n has two odd digits :   n --> 22 --> 202 --> 301 --> 123  k = 4       c) If n has three digits then we have four following cases:   1. n = 123,   k = 0. 2. n <> 123, n has three even digits : n --> 303 --> 123         k = 2    3. n <> 123, n has two even digits : n --> 213 --> 123          k = 2   4. n <> 123, n has only one even digit : n --> 123                k = 1  5. n <> 123, n has three odd digits : n --> 33 --> 22 --> 202 --> 303 --> 123  k = 5
d) If n has more than three digits then after one or more steps we get a three digits
which we discussed in this in  (c).

So for each positive integer by applying this rule we always end with 123.

The smallest integer and the smallest prime for k = 4 is 11.
11 --> 22 --> 202 --> 301 --> 123    k = 4.

The smallest integer  for k = 5  is 1.
1 --> 11
The smallest prime for k = 5  is 3.
3 --> 11 --> 22 --> 202 --> 301 --> 123    k = 5.

***
It is interesting that for some numbers d, d = 10000, 10001, ... , 10100, ...  k for all
d-digits integers is 4.

***

 Records   |  Conjectures  |  Problems  |  Puzzles