Problems & Puzzles: Puzzles
Puzzle 108. Methods
Smith number is such that the sum of
its digits is the sum of the digits of all its prime factors
666 = 2*3*3*37 & 6+6+6 = 2+3+3+(3+7
Method 1: Multiply any prime-Repunit (*) greater than 11 by 3304
This way of generating Smith numbers (**) is described by Paul Hoffman in his book "The man who loved only numbers", p. 222, and also by Pat Costello in his Web site. The method was found by Sham Oltikar & Keith Wayland of the University of Puerto Rico
I was intrigued by this conspicuous factor (3304) & decided to find others, that I was supposing must be larger than 3304. For my surprise there are four smaller ones: 1540, 1720, 2170 & 2440. After 3304 there are many many others, organized by families...
Question 1. Would you like to extend this sequence of factors (that produce Smith numbers when multiplied by prime-Repunits) and show the way they are organized? Can these factors be prime numbers? Why?
Method 2: Multiply any prime P0,1 (a prime composed only by 0's & 1's) by certain factors F
This method is also mentioned by Hoffman in the same book and page, and is also a result of the work of Oltikar & Wayland. But in this case no idea is given about the characteristics of these F factors. In particular I would like to discuss about the size of the least F factors for each P0,1, that I would call Fº(P0,1).
Here are some examples of Fº(P0,1):
the corresponding Smith number is 101*2=202
Question 2. Can you bound F*(P0,1) against P0,1?
Question 3. Do you now or devise other methods for generating Smith numbers?
Question 4. In particular do you know or devise any way for generating sequences of Smith numbers (SN), that is to say starting with an initial SN then apply a regular procedure that generates recursively other SN's.
(**) Only in this particular sense, the Smith numbers generated by this method are similar to the perfect numbers: every time a Mersenne prime number is found, the corresponding perfect numbers can been calculated. Mutatis mutandis, every time a new prime-repunit is found, at least one Smith number can be calculated.
Other references: http://mathworld.wolfram.com/SmithNumber.html
The first contribution to this old puzzle came from Jon Wharf:
Q1: I found the following 20 "Smith generators" less than 100000:
There were 42 between 10^5 and 10^6 and another 84 between 10^6 and 10^7. As you say I could easily have found many more by going higher. From these, every time a new repunit prime is found, at least 146 new Smiths can be generated! Much better than just one perfect number per Mersenne prime.
Only two more after 3304 were not 0 mod 10:
and my largest was:
They all are required to have a digital sum of 10. They must also have a digital factor sum DFS() of some multiple of 9.
So of course they're not prime, and I would organize them by their DFS - 18, 27, 36 or 45 in the range I examined.
For the first four and the sixth, they will generate Smiths with 11. All those below 100000 also work with R4=1111 which, although not prime, is Smith. This represents the point where the "overlapping" of the generator by the repunit stabilizes and stops adding ten onto the digital sum of the product, just adding the central one from that length on.
At some point a new family will appear with a digital sum of 100 but working out the digital factor sum required will be tricky.
Question 2 was also interesting. To make a Smith from a P0,1 you need a certain strength of ratchet (as I thought of them).
If the digit sum of the prime p is n, then the ratchet number R you want must have DS(R)*n=DFS(R)+n. That is, DFS = n(DS-1). I also limited the digital sum of R to less than 10. Then Rp is Smith.
For certain P0,1 digital sums then, the smallest ratchets are:
For all of these except 140, they are also good for primes with digits 2 or 3 in - for example 21*23 = 483, DS=DFS=15. 1001 (13) and 200 (16) will deal with digit 4 as well. These ratchets will also work on Smiths with suitably small digits, egg 1111*140 = 155540, DS=DFS=20.
Also, consider the number 413 - digit sum 8 and digit sum of factors 21. It is thus a 3-ratchet (21/(8-1)=3) - useless for practical Smith creation. But wait! add a zero and it's a 4-ratchet (28/(8-1)=4) - add another and it's a 5-ratchet, and so on. 413*10^(n-3) is an n-ratchet!!! For delicate work, 1110011111*10^(n-7) n>7, is also an n-ratchet.
Question 3 leads on from the techniques of Q2. By multiplying a number with low digits by the right ratchet-type number, worrying about the algebra of changing DS and DFS, we can make a Smith out of some of such numbers. Using the following "magic" ratchets:
R DFS(R) mod 7
12 7 0
Now calculate DS(n)*3-DFS(n), pick the right mod-7-ratchet R and add (DS(n)*3-DFS(n)-DFS(R))/7 zeroes to the ratchet.
3233133 has DS=18, DFS=33. 3*DS(n)-DFS(n) = 21 == 0 mod 7. R=12 and add (21-7)/3 = 2 zeros. Then 3233133*1200 = 3879759600 is Smith, DS=DFS=54.