Problems & Puzzles:
For sure you already know what a
is (D. R. Kaprekar).
The first few base 10
self numbers are
1, 3, 5, 7, 9, 20,31,
42, 53, 64, ... (sequence
The following recurrence relation
generates infinite base 10 self numbers:
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
C(1571) = 888888.......88901449
C(19457) is prime. 888888888.........8889044537. (19458
1. Restrict the search for
candidates n such as n + sumofdigits(n) = s to the interval [s -
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.
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
2*10^8000 + 160679 is prime and self number
2*10^1000 + 248339 is prime and self-number in base 10
and self-number in base 2
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
Q1. I could only find that after c(120) the next prime is c(1571)
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
effectively smallest number to check.
Anyway, checking if a number is self costs much less than checking
if it is
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
:= s + m; z := (z - m)/10; if z = 0 then break end if end do;
maxdig := proc(n) local z,m,j,s; z := n; s := 0; for j do m := z mod
:= s + 9; z := (z - m)/10; if z = 0 then break end if end do;
isself := proc(n) local z,s,t; global digadd, maxdig; s := n -
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
such a k or n otherwise. Running time is proportional to the number
digits of n.
Q3. The number of selfnumbers in 1000, 10000 and 100000 numbers is
and 9784. The number of selfprimes in 1000, 10000, 100000 primes is
and 8854 self primes. It seems that the frequency of selfnumber in
and in general is similar.
It follows the list of the self primes between the first 100 primes
that N^(10*k) for N=2,3,10. Each list contains k, the number of self
and the selfprimes. The frequency of selfprimes in the prime
between 6 and 16%.
[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,
[1, 8, [10000000469, 10000000537, 10000000649, 10000000963,
10000001593, 10000002113, 10000002403]]
m=2^24036583-1 is prime & self
My method basically used the following theorem to reduce the
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
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
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
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
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
Later he added (See Puzzle 374)
The theorem I stated last time did not deal with numbers that
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
However, the following theorem describes a method that will describe
the selfness of any number n in terms of at most two significantly
Let s(n) denote the sum of digits of integer n, and write S(n) for
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:
are negative or self.
From this theorem, he proved the following:
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
"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."