Problems & Puzzles: Puzzles

Puzzle 394. No shared digits between composites and its prime factors. In the  "Did you know" section of the main page of the web site of my friend Shyam Sunder Gupta, currently (March, 07) we can see the following curio: 8589934592 x 116415321826934814453125 (No zero in both numbers) = 1000000000000000000000000000000000 This is the largest known example of this kind. The obvious puzzle arising from this curio is to find non-trivial examples of composite numbers such that its prime factors share no one single digit with the digits of the composite number. Regarding this puzzle the example giving by Shyam follows is not a solution acceptable because of the shared digit "1". Perhaps, but not for sure, the most obvious candidates to produce large solutions are the composite repdigit numbers. I made a little search seeking large repdigit composites & solutions for this puzzle and found the following example, perhaps a good starting point for brave puzzlers: (8)93 =  2 ^ 3 x 3 x 37 x 2791 x 6943319 x 57336415063790604359 x 900900 900900900900900900900900990990990990990990990990990991 Questions. 1. Find larger non-trivial solutions. A trivial solution is one that follow a potentially infinite pattern. Examples of patterns that I have found during my very short search for non-trivial solutions: (4)n = 2*2*(1)n, for all n such that (1)n is prime (6)n = 2*3*(1)n, for all n such that (1)n is prime (8)n = 2*2*2*(1)n, for all n such that (1)n is prime (9)n = 3*3*(1)n, for all n such that (1)n is prime If the factors are not necessarily asked to be primes then, apart from the above models, this is another example of trivial solution: (1)3.n = 37*(003)n 2. Find other trivial solutions (patterns).

---

Contributions came from Anton Vrba, Farideh Firoozbakht, Bernardo Boncompagni & Jim Howell.

***

Anton wrote:

4(8)₆₀₇488 has prime factors 2^3*11*(5)₆₀₈1 and belongs to a family of semi-trivial solutions found as follows: 

If  the factors of  (1)_k  do not include the digits 4 and 8 that is when k=2,3, 4, 6, 8, 9, 12,13, 17, 18, 19, 23, 24, 36, 38, 39
... and if  ((5(0)_k-1)_n+1) is prime (or does not include the digits 4 and 8) and k>2 then  (4)_k*n(8)_k  is a semi-trivial solution
to this problem. and searching for n<200 and above k>3, then ((5(0)_k-1)_n+1) = 5*(10^{k – 1})*(10^k*n - 1)/(10^k - 1) + 1 is prime
for {k,n}={3,2},{3,8},{3,21},{4,3},{6,2},{6,15},{6,51},{8,2},{8,5},{12,126},{17,12}and {23,5)  

examples:

k=3 and n=2:  444444888 =2^3*3*37*500501  or

k=17 and  n=12: (4)₂₀₄(8)₁₇=2^3*2071723*5363222357* ((5(0)₁₆)₁₂+1)

The problem’s and the above cases are examples when the composite is composed of one or two repeating digits. If on the other hand the allowed digits in the factors are limited and then exclude these from the composite, following solutions to this problem can be found:

Let p be a prime number consisting of only digits 1 and 2  (i.e 211) the 4*p is a trivial solution to this problem, or

Let p be a prime number of the form 11(061)_n  or combinations thereof then p*8 is a trivial solution to the problem.

Other solutions using two digit factors:

5428(1)_n245263 has factors 7 x 997 x (7)_n+497

and (7)_n+497 is prime for n+4= 11, 38, 41, 72, 498, 527, 762, 811 ....

further examples are semi-primes of the form

601(2)_n18529 has factors 773 x (7)_n+43
601(2)_n190701 has factors 773 x (7)_n+437
601(2)_n1912421 has factors 773 x (7)_n+4377 , n=1, 23, 170, 1077
601(2)_n19129621 has factors 773 x (7)_n+43777

examples:

542811111111111245263 = 7 x 997 x 77777777777777797 or
60121912421 = 773 x 77777377 

Finally, brute force combinatorics  based searches result in solutions like the below set of  four 114+ digit composite
that all exclude digits 0,1,2 and 3 the latter which is also excluded from the prime factors

2 x 2 x 2 x 11 x 1000001000001000000000001000001000001000\
001000000000000000001000000000000000001000000000000000001 x
{10101011101010101, 10101110101010101, 11010101101010101 or
101011010101010101} = {8888898657787546658657777777778657\
78754666754665865776888888888888976888888888888888976888\
888888888888976888888888, ...}

Carlos asked  “Could you send solutions such that all digits are present in the set of the composite & its prime factors”  the answer is yes and a set of 72 was quickly found using the same root, the first few are:

2 x 2 x 2 x 11 x 1000001000001000000000001000001000001000\

 001000000000000000001000000000000000001000000000000000001 x
{10101111111110111, 10101111111111101, 10111111101011111, 10111111101110111, 11101110111011111,....,
111101010101010111101}=
{88889866667635644346754657866666667635644435644346754568\
9768888897777777689768888897777777689768888897777777689768, ....}

Solutions with all digits represented are fairly common, as above and many others are found with minimum computational
efforts.  More difficult to find are solutions to this problem with added condition that a further digit is excluded. 

For example, here is a set of four numbers that excludes digits 3 and 4 from both the composite and its prime factors

2 x 2 x 2 x 11 x 100000100000000000100000100000000000000\
0001000000000001000000000001000000000000000001000000000\
000000001000000000001 x {10101011101010101, 101011010101010101, 10101110101010101 ,
101011010101010101} = {88888986577786577777777786577786577688888888888897688977\
77769768897777769768888888888888889768888888888888889768\89777776976888888888, ...}

Another interesting solution is the 158 digit composite that excludes digits 0,1,2, and 4 and only has two numbers of the digit 3 and 9.

2 x 2 x 2 x 11 x 101 x 10001000100010001000000000000000100010001 x
10000010000000000010000010000000000000000010000000000010000\
00000001000000000000000001000000000000000001000000000001 = 88888977777777777865777865777778666666666753777777777867555553777865777777777777777865\
777777777777777865777776888978666665777776888888888888888888888888888888 

The next question to ask is:

Let D_c be a set of  digits that make up a non trivial composite number, and its prime factors are a made up of the digits in the set D_p,  and D_e is the set of digits excluded.

Find large non trivial examples for all possible combinations of D_e,  D_c and D_p with the condition the intersection of sets D_c and D_p is an empty set.

Above examples are for D_p={0,1,2} and  D_e = {3}, {4}, {3,4}.

For D_p={0,1,2} and D_e = {5}  a solution is

2 x 2 x 11111011111011011 x 1000001000000000001000001\
0000000000000000010000000000010000000000010000000000\
00000001000000000000000001000000000001 = 48888497776897336897336897776897336848448448888448888\
4973368488884973368488884484484488884488884484484488\
884488884973368488884484484

***

Farideh wrote:

1. A trivial pattern:   9(n).0 = 2*3*3*5*1(n) for all n such that 1(n)=(10^n-1)/9 

is prime.

 

Also we have the following pattern for all non-negative integers n, m & r where

both numbers 2(m+1).7(n).3 &  1(m+n+r+2) are prime.

 

2*3*3*2(m+1).7(n).3*1(m+n+r+2) = 4(m).5(n).45.9(r).5(m).4(n).54

 

Examples:

 

m = n = r = 0             2*3*3*23*11=4554

 

m = n = 0 & r = 17     2*3*3*23*11111111111111111 = 45.9(17).54 = 459999999999999954

 

m = 1000, n = 967 & r = 86453 - (1000 + 967+ 2) = 84484  (please see  A004023) .

2. For all non-negative integers m & n  such that both numbers

8(m+n+3).9  and  844.9(m) are prime we have the following solution.

 

               8(m+n+3).9 * 844.9(m) = 75.1(m).0.2(n+1).316.1(m)

 

Example: m = 2,  n = 8 

   

88888888888889 * 84499 =  75.1(2).0.2(8+1).316.1(2) = 7511022222222231611

 

3. For all non-negative integers m & n  such that both numbers

8(m+n+3).9  and  806.9(m) are prime we have the following solution.

                8(m+n+3).9 * 806.9(m+1) = 717.3(m).2.4(n).534.1(m+1)

 

Example: m = 2,  n = 8 

 

88888888888889 * 806999 = 717.3(2).2.4(8).534.1(3) = 71733244444444534111

Bernardo wrote:

1) you skipped the mother of all trivial solutions, 2^n*5^n=10^n :-)
2) your approach is good if you already have a good number of
prefactored large numbers, but if you try factoring random huge numbers
you'll find yourself stuck in the factorizations too soon. Instead, I
tried taking powers of small, convenient primes and multiplying them. As
I said, I didn't work on this for long but here's an example of what
this approach can deliver:
2^168 (51 digits) does not contain the digit 2;
2^101*2333^6 (51 digits as well) does not contain the digits 2 and 3.

A random n-digit number has approximately a (1-k/10)^n chance of not
containing k digits.

Last, of course, this puzzle could be expressed in any base but I didn't
explore any other than 10.

***

Jim wrote:

20(n)1 = 3 * 6(n)7  for all n such that 6(n)7 is prime.

 

 

The first few examples (with n = 0, 1, 5, 7,  8, 10, and 19) are:

 

21 = 3 * 7 (very trivial)

 

201 = 3 * 67

 

2000001=3 * 666667

 

200000001=3 * 66666667

 

2000000001=3 * 666666667

 

200000000001=3 * 66666666667

 

200000000000000000001 = 3 * 66666666666666666667

***

Emmanue Vantieghem wrote on April 15, 2015:

I think the 91-digit number

m = 2794900729589070540080665964706270079685505477662622722490042877072885564679875652689929447

merits also some attention.

It misses the digits  1  and  3  but every of its twenty prime factors has only the digits 1 and/or 3 :

m = (3^2)*11*13*(31^2)*(113^2)*131*311*(313^3)*331*(3313^2)*(3331^2)*11113*(11131^2)*11311*13313*13331*31333*(33113^2)*33311*(33331^2).

***

---