Problems & Puzzles: Puzzles

Puzzle 108. Methods for generating Smith numbers

A Smith number is such that the sum of its digits is the sum of the digits of all its prime factors

Example: 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):

F(101)=2; the corresponding Smith number is 101*2=202
F(10111)=140; the corresponding Smith number is 10111*140=1415540
F(101111)=21; etc...
F(1011001)=140; etc...
F(1100101)=140; etc...

...

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.

____________
Notes:

(*) Repunit is a number composed only by 1's. They are usually symbolized by R(n) where n is the quantity of 1's of the number; currently R(n) is known to be prime only for n=2, 19, 23, 317, 1031 & 49081 (this last is only a probable repunit-prime)

(**) 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:

1540
1720
2170
2440
3304
6040
10270
11080
11620
16030
21340
22330
24130
24220
30070
34120
40330
40420
62020
70120

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:

520201
3222001

and my largest was:

7000030

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:

DS(p) Ratchet

2 2
4 140
5 21
7 120
8 201
10 1020
11 1011
12 2100 (not prime of course but you might get a low digit Smith)
13 1001
14 12000
15 20100 (as above, e.g. with Smith 2123331)
16 200

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
10011 22 1
1011 16 2
10101 24 3
10002 25 4
1101 19 5
111 13 6

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.

Example:

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.

***

 


Records   |  Conjectures  |  Problems  |  Puzzles