Problems & Puzzles: Puzzles

Puzzle 373. Self primes For sure you already know what a self number is (D. R. Kaprekar). The first few base 10 self numbers are 1, 3, 5, 7, 9, 20,31, 42, 53, 64, ... (sequence A003052 in OEIS). The following recurrence relation generates infinite base 10 self numbers: C(k)=8.10^(k-1)+C(k-1)+8; C(1)=9 This recurrence gives self-prime-numbers for k=2, 30, 35, 111, 119, 120,...? Q1. Find larger k values such that C(k) is prime. Q2. Find an efficient algorithm in order to compute that a given n value is a self number or not. Q3. Apply your results in Q2 in order to find larger/distinct prime numbers than the obtained in Q1.

---

Contributions came from Jacques Tramu, Farideh Firoozbakht, Daniele DeGiorgi & Luke Pebody.

Luke found the most beautiful/efficient approach in order to test if a prime is self or not. Accordingly, he tested the Mersene primes and got the largest Mersene & Self prime  currently known: 2^24036583-1

***

Tramu wrote:

Q1.

C(1571) = 888888.......88901449 is prime.
C(19457) is prime. 888888888.........8889044537. (19458 digits)

 

Q2.

1. Restrict the search for candidates n such as n + sumofdigits(n) = s to the interval [s - numberofdigits(s)*9,...,s-1] .

 

2. Not an algorithm, but you can chose large numbers of form 10^k + small number. The sum of digits is quickly computed.

For exemple 10^10000 + 100003, 100044, 100055, 100066, 100077 , ...are self numbers.

 

Q3.

10^2000 + 100459 is prime and self number (2001 digits)
2*10^2000 + 112127  2001 digits
2*10^3000 + 101259  3001 digits
2*10^4000  + 102743  4001 digits
2*10^5000  + 529317  5001 digit

2*10^6000 + 346887, + 395487, + 397557 are primes and self numbers
2*10^8000 + 160679 is prime and self number

 

Curios :
2*10^1000 +  248339  is prime and self-number in base 10 and self-number in base 2

 

 

Farideh wrote:

Answer to Q1: Next term of the sequence  2, 30, 35, 111, 119, 120, ... is 1571 and there is no further term up to 18888

Daniele wrote:

Q1. I could only find that after c(120) the next prime is c(1571) then there
are no other primes at least for k < 5650.

Q2. It is enough to check the 9*log(n) numbers preceding n to check if n is
selfnumber (log in base 10).
Testing all of them is possibly less time consuming than to calculate the
effectively smallest number to check.
Anyway, checking if a number is self costs much less than checking if it is
a prime.

Following functions in Maple can be used

digadd := proc(n) local z,m,j,s; z := n; s := 0; for j do m := z mod 10; s
:= s + m; z := (z - m)/10; if z = 0 then break end if end do; RETURN(n+s)
end;

maxdig := proc(n) local z,m,j,s; z := n; s := 0; for j do m := z mod 10; s
:= s + 9; z := (z - m)/10; if z = 0 then break end if end do; RETURN(s) end;

isself := proc(n) local z,s,t; global digadd, maxdig; s := n - maxdig(n); if
s < 0 then s := 1 end if; for t from s to n do if digadd(t) = n then
RETURN(t) end if; end do; RETURN (n); end;

isself(n) returns the smallest k such that k + digsum(k) = n if there is
such a k or n otherwise. Running time is proportional to the number of
digits of n.

Q3. The number of selfnumbers in 1000, 10000 and 100000 numbers is 102, 983
and 9784. The number of selfprimes in 1000, 10000, 100000 primes is 95, 873,
and 8854 self primes. It seems that the frequency of selfnumber in primes
and in general is similar.

It follows the list of the self primes between the first 100 primes larger
that N^(10*k) for N=2,3,10. Each list contains k, the number of self primes
and the selfprimes. The frequency of selfprimes in the prime examined lies
between 6 and 16%.

...

N=2
[1, 8, [1087, 1109, 1223, 1289, 1447, 1559, 1627, 1693]]
[2, 5, [1048661, 1049089, 1049201, 1049471, 1049717]]
[3, 12, [1073741827, 1073741939, 1073742077, 1073742233, 1073742391,
1073742773, 1073743291, 1073743313, 1073743337, 1073743381, 1073743403,
1073743739]]
...

N=10

[1, 8, [10000000469, 10000000537, 10000000649, 10000000963, 10000001437,
10000001593, 10000002113, 10000002403]]
...

[10, 6,
[100000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000004317,
1000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000007443,
1000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000015139,
1000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000016443,
1000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000016599,
1000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000027309]]

***

Luke Wrote:

m=2^24036583-1 is prime & self

...

My method basically used the following theorem to reduce the checking
of whether or not a big number is self to whether or not a smaller
number is self.

Let s(x) denote the sum of the digits of x

Theorem: Suppose that n is an integer with k digits, such that the decimal expansion of n ends with the integer l>=9k. Then n is self iff l+s(l)-s(n) is self.

Proof: There exist integers a and t such that n=10^a*t+l and 10^a>l.

Every integer p<n with n=p+s(p) must have p<n<10^k, and so s(p)<9k<=l.
Thus p=10^a*t+(l-s(p)) is made up of the number t followed by the
number l-s(p) (with maybe some 0's afterwords).

Thus the integers p<n with n=p+s(p) are exactly the integers 10^a*t+k
with k<l and k+s(t)+s(k)=l. Thus there is such an integer if and only
if there is an integer k such that k+s(k)=l-s(t).

But by the definition of t, s(n)=s(t)+s(l), so n is self if and only
if there is an integer k with k+s(k)=l+s(l)-s(n).

...

A small example: Let n=2^44497-1. It has k=13395 digits, and the smallest terminating
string of n that is at least 9k=120555 is l=228671. Finally s(n)=60337.

Thus n is self iff 228671+(2+2+8+6+7+1)-60337=168360 is self by the theorem.

168360 has k=6 digits, and the smallest terminating string of n that is at least 9k=54 is l=60. Finally s(n)=24. Thus n is self if 60+6-24=42 is self.

The method can no longer be used, but 42 can easily be checked to be self.

Later he added (See Puzzle 374)

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.

From this theorem, he proved the following:

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

***

What I [CR] can add now (Oct, 6, 2006) is that this algorithm in order to test the selfness of a number seems to be an improvement to the already discovered & published by Kaprekar on 1975?. Taken from the T. Trotter's page:

"D. R. Kaprekar's method of testing a number, N, to see if it is a self-number is as follows. Obtain N's digital root by adding its digits, then adding the digits of the result and so on until only one digit remains. If the digital root is odd, add 9 to it and divide by 2. If it is even, simply divide by 2. In either case call the result C. Subtract C from N. Check the remainder to see if it generates N. If it does not, subtract 9 from the last result and check again. Continue subtracting 9's, each time checking the result to see if it generates N. If this fails to produce a generator of N in k steps, where k is the number of digits in N, then N is a self-number."

***

 

---