Problems & Puzzles: Puzzles

Puzzle 374. Self numbers As soon as I published the results for the Puzzle 373, I asked to the four collaborators  of that puzzle (Pebody, Firoozbakht, Tramu & Degiorgi) the following perhaps naive question (1/10/2006): Dear Friends: Can you discover the law behind consecutive self numbers? It seems to exist a simple regularity for this quantity... As no direct answer came from any of them, I realized that a new puzzle was already being born :-) During the rest of the days I read other pages related to the self numbers and right now I have more questions but zero solutions ;-) Let's define gs(i)=s(i+1)-s(i), i>0, where s(i+1) & s(i) are consecutive self numbers, s(1)=1, s(2)=3, ... Q.1.1 What can you say about a general law for gs(i)? Q.1.2 Can you demonstrate that gs(i) can not be equal to 1? Q.1.3 Apparently gs=11 has a relative frequency a lot higher than the other possible values. Can you explain this fact? Q.2 What powers x of 10, other than 6 & 16, make 10x a self number? Now let's switch to non-self numbers (NSN). Kaprekar noticed that some non-self numbers could have more than one generator. As a matter of fact he discovered the smallest numbers with k generators, for k=2, 3, & 4: For K=2, NSN=101 because it is generated by 91 & 100 For K=3, NSN=10,000,000,000,001 because it is generated by 10,000,000,000,000, 9,999,999,999,901, and 9,999,999,999,892. For K=4, NSN= 1,000,000,000,000,000,000,000,102, because it is generated by W, X, Y & Z. Q3. Find W, X, Y & Z Q4. Find the smallest NSN having K generators for K=5, 6, ... Do you devise a systematic approach in order to solve this question?

---

Contributions came from Luke Pebody (Q2 & Q4), Jacques Tramu (Q1.1) & Farideh Firoozbakht (Q1, Q2 & Q3)

***

Luke wrote:

Q2. 10^k is a self number if and only if 9k-1 is a self number.

Q4. The smallest I have found is 10^111111111124+102.

Proof for Q2:

The theorem I stated last time did not deal with numbers that were of
the form d.10^a+k where d is a one-digit number and k is something
smaller than 9a. Then my method of last time can give no improvement.
However, the following theorem describes a method that will describe
the selfness of any number n in terms of at most two significantly
smaller integers.

Let s(n) denote the sum of digits of integer n, and write S(n) for n+s(n).

Theorem:
Suppose that n is a positive k-digit integer where k>=3, and let a be
an integer such that k>a, but 10^a>=9k. Then split the digits of n up into two - write n=m.10^a+t, where 0<=t<10^a.

Then n=m.10^a+t is self if and only if both of the numbers:
   [t-s(m)] &
   [s(m-1)+9a-(t+1)]
are negative or self.

Proof:
Let f(n) denote the number of positive integers p such that S(p)=n. We
will show that f(n)=f(t-s(m))+f(s(m-1)+9a-(t+1)).
Clearly this is sufficient, because f(n)=0 if and only if n is negative or self.

Let T={p>0:S(p)=n}. Then split T up into T1={p in T:p>=m.10^a} and
T2={p in T:p<m.10^a}.

For any p in T1, p can be written as m.10^a+u. Since p<n, u<t and
hence u<10^a. Thus s(p)=s(m)+s(u).
Thus S(p)=m.10^a+s(m)+S(u). This is to say that such p has S(p)=n,
precisely if S(u)=t-s(m). Thus the number
of elements of T1 is f(t-s(m)).

For any p in T2, p can be written as
(m.10^a-1)-u=(m-1).10^a+((10^a-1)-u). In order that S(p)=n, it must
follow that
s(p)=n-p=t+1+u. However p is of at most k digits, so s(p) is at most
9k, so u is at most 9k-1 and is less than 10^a.
Then the number (10^a-1)-u can be written by writing out u to a
digits, and subtracting each one from 9. Thus
s(p)=s(m-1)+9a-s(u), and hence S(p)=(m.10^a-1)+s(m-1)+9a-S(u). This is
to say that such a p has S(p)=n precisely
if S(u)=s(m-1)+9a-(t+1). Thus the number of elements of T2 is
f(s(m-1)+9a-(t+1)).

Thus f(n)=f(t-s(m))+f(s(m-1)+9a-(t+1)).
QED

Corollary:
10^a is self if and only if 9a-1 is.

Proof:
Set m=1 and t=0 in the above. Alternately, if 10^a=S(p), then
p<=10^a-1. Thus p=(10^a-1)-u for some integer u, and then
s(p)=9a-s(u), and hence S(p)=(10^a-1)+9a-S(u)=10^a+((9a-1)-S(u)).

Thus, for p<10^a, S(p)=10^a if and only if 9a-1=S(u).
QED

***

Let me [CR] add an example of new theorem discovered by Pebody:

n=m.10^a+t is self if and only if both of the numbers:
   [t-s(m)] &
   [s(m-1)+9a-(t+1)]
are negative or self.

Mr. Tramu stated in Puzzle 373 that 10^2000+100459 is self.

According to Pebody's theorem:

1*10^2000+100459 is self iff:

100459-1=100458 is self?, and
0+9*2000-(100459+1)<0

100458=1*10^5+458 is self iff:

458-1=457 is self?
0+9*5-(458+1)<0

But 457 is self according to A003052

So, 10^2000+100459 is self.

***

Jacques wrote:

Q1.1

--  gs(i) is either 11 or = 2 (mod 13)  : 2,15,28,41,....

--  in the interval [10^n...10^n+10^p]

     the number of gaps of size( 2 + k*13 )   is   9* 10^(p-3-k).

 

(any n, k>=0,  p> 3, p-3-k >=0 )

 

Ex : [1..10^9]  :   90000 gaps of size 28.

[N.B. Luke Pebody sent a short note on this issue: "Gap sizes are not all equal to 11 or equivalent to 2 modulo 13: There are gaps of:

101: 10^13+8 to 10^13+109
118: 10^14+4 to 10^14+122
131: 10^15+2 to 10^15+133
204: 10^24+6 to 10^24+210..."]
 

***

Farideh wrote:

Q.1.2: gs(i) can not be equal to 1 because if s(i+1)=n is a self number then

there exists a number j where  j<>9 (mod 10)  and  j+sod(j)<n<(j+1)+sod(j+1)

but since  j<>9 (mod 10)  we have  (j+1)+sod(j+1)=(j+1)+sod(j)+1=j+sod(j)+2

hence  j+sod(j)<n<j+sod(j)+2 and so n-1= j+sod(j)  & n+1=(j+1)+sod(j+1),

the first equality shows that s(i) is less than n-1 so gs(i)>1.

 

Q2: All numbers n such that 10^n is a self number up to 2500 are:

 

6,16,26,36,46,57,67,77,87,97,107,116,126,136,146,157,167,177,187,197,207,217,226, 236,246,257,267,277,287,297,307,317,327,336,346,357,367,..., 2487,2497

 

Q3:

W=10^24-107=999999999999999999999893

 X=10^24-98=999999999999999999999902

Y=10^24+91=1000000000000000000000091

Z=10^24+100=1000000000000000000000100

 

***

 

---