Problems & Puzzles: Puzzles

Puzzle 472. What is the second solution? Qu Shun Liang sent the following nice puzzle: Suppose you have a composite number n whose prime numbers concatenated in ascending order produce another number m (m=p1&p2&p3....&pn). It may happen that n divides m. When it happens we we call n a CSDN number. The smallest CSDN number is 28749 because 28749=3*7*37*37 and because 28749 divides to 373737. QSL sent four more solutions (that I will not show by now) and the following two questions: Q1. What is the second largest CSDN number? Q2 Is there an  CSDN n number such that m/n=k where k=3 o 7? Q3. Do you devise a smart approach to get CSDN numbers?

---

J. K. Andersen wrote (Dec 08)

Q1. The second CSDN number is n = 21757820799 = 3*11*13*683*74257,
where m = 3111368374257 and m/n = 143.

Q3. I found 119 large CSDN numbers with an approach in
http://zdu.spaces.live.com/blog/cns!C95152CB25EF2037!132.entry

Let 10^b+1 = p1*p2*...*pi * r, where p1 to pi is a selected subsequence of
the prime factors written in non-decreasing order with repeated factors
allowed, and r is the product of whichever prime factors are not selected in
p1 to pi.
Let P be the concatenation of p1 to pi. If P is a prime with b digits then
n = p1*...*pi*P is a CSDN number, because the concatenation of the
prime factors of n is:
m = (P concatenated with P) = P*10^b + P = (10^b+1)*P = p1*...*pi*r*P = n*r.
The factorization of m/n = r shows which prime factors were not used in the
construction of P.

This method was used with factorizations of 10^b+1 from
http://homepage2.nifty.com/m_kamada/math/10001.htm and other sources. All
complete factorizations I could find below 10^5000+1 were examined.
PARI/GP tested for probable primes P for all prime factor subsequences giving
b concatenated digits. Marcel Martin's Primo later proved all the primes P.
This included 85 titanic proofs.
A total of 119 CSDN numbers were found for 25 values of b:
b = 13, 33, 45, 70, 75, 99, 101, 105 (2 numbers), 117 (2), 119, 123,
143, 165 (2), 225, 231, 315, 429, 483, 510, 570, 585 (8), 630 (2), 805,
1155 (78), 1530 (7).

Note that 78 of the 119 numbers are for b=1155. 10^1155+1 has 46 prime
factors with a total of 1179 digits. Many of the factors are small and there
are a lot of ways to select a subsequence with 1155 digits.

Below is listed the value of b, the number of digits in n, and the value of
m/n = r for the 119 CSDN numbers. For space reasons, other data such as the
complete factorizations and selected factors of 10^b+1 are not listed but can
be mailed on request. The selected factors can be reconstructed from the complete factorizations by removing the shown prime factors of m/n = r.

The complete data is shown here for the smallest solution with b=13.
10^13+1 = 11*859*1058313049.
The selected p1*p2 = 859*1058313049 with r = 11.
P = concatenation of (p1, p2) = 8591058313049.
n = p1*p2*P = 859*1058313049*8591058313049 = 7810053011863508278028459.
m = concatenation of (p1, p2, P) = 85910583130498591058313049 = n*r.

b=13: n25, m/n = 11 = 11
b=33: n63, m/n = 847 = 7*11*11
b=45: n85, m/n = 118183 = 13*9091
b=70: n135, m/n = 42521 = 101*421
b=75: n145, m/n = 100001 = 11*9091
b=99: n193, m/n = 16093 = 7*11*11*19
b=101: n198, m/n = 1213 = 1213
b=105: n203, m/n = 1688687 = 7*7*11*13*241
b=105: n204, m/n = 889889 = 7*7*11*13*127
b=117: n228, m/n = 5081087 = 11*461917
b=117: n230, m/n = 35321 = 11*13*13*19
b=119: n235, m/n = 1133 = 11*103
b=123: n243, m/n = 1001 = 7*11*13
b=143: n279, m/n = 3515887 = 859*4093
b=165: n321, m/n = 868848851 = 13*23*331*8779
b=165: n322, m/n = 364103641 = 11*11*331*9091
b=225: n443, m/n = 63989371 = 2161*29611
b=231: n455, m/n = 54981983 = 7*23*127*2689
b=315: n617, m/n = 25892823498373 = 13*241*9091*909091
b=429: n846, m/n = 2384353896223 = 13*183411838171
b=483: n957, m/n = 6928071361 = 127*2689*20287
b=510: n1006, m/n = 180915858034489 = 3061*9901*5969449
b=570: n1126, m/n = 88829973141229 = 61*4789*304077901
b=585: n1156, m/n = 270778882116289 = 859*1171*9091*29611
b=585: n1157, m/n = 70410178476997 = 211*241*6397*216451
b=585: n1157, m/n = 11784424106699 = 19*131*241*2161*9091
b=585: n1157, m/n = 7676989978223 = 19*131*157*2161*9091
b=585: n1156, m/n = 152740263812929 = 13*859*29611*461917
b=585: n1158, m/n = 6800808382979 = 13*131*157*859*29611
b=585: n1157, m/n = 14422563924197 = 11*13*211*9091*52579
b=585: n1158, m/n = 229901360689 = 7*11*13*13*131*157*859
b=630: n1241, m/n = 14881040339039527321 = 3541*9901*424451728681
b=630: n1242, m/n = 769507652913761981 = 29*27961*226549*4188901
b=805: n1599, m/n = 19294293407 = 47*691*594091
b=1155: n2288, m/n = 32758998481427805579493 = 4093*8779*9091*24179*4147571
b=1155: n2288, m/n = 53289558077379252028009 = 2689*8317*8779*459691*590437
b=1155: n2288, m/n = 13846186726610143517197 = 2161*2689*8779*459691*590437
b=1155: n2288, m/n = 32984782402052457477863 = 463*5171*459691*29970369241
b=1155: n2288, m/n = 14822148760945952616569 = 463*2689*590437*20163494891
b=1155: n2288, m/n = 8361011816557098954691 = 331*463*101641*590437*909091
b=1155: n2289, m/n = 1328136106623479478419 = 241*2689*101641*20163494891
b=1155: n2289, m/n = 5360842122457225456007 = 211*463*2161*5171*8317*590437
b=1155: n2289, m/n = 2208121023188877759973 = 211*331*2689*3851*5171*590437
b=1155: n2289, m/n = 2454826688374180441693 = 211*241*463*5171*20163494891
b=1155: n2289, m/n = 1064897978224489321049 = 127*211*5171*8317*9091*101641
b=1155: n2290, m/n = 632314148066442988877 = 127*211*241*2689*8779*4147571
b=1155: n2289, m/n = 3360760943225046747853 = 23*127*463*4147571*599144041
b=1155: n2290, m/n = 331143905953354113317 = 23*127*241*331*8317*170873011
b=1155: n2289, m/n = 6670397028068608389971 = 13*211*4093*8779*9091*7444361
b=1155: n2289, m/n = 989635605604824825049 = 13*211*241*8317*24179*7444361
b=1155: n2290, m/n = 86664073917449158481 = 13*127*241*331*3851*170873011
b=1155: n2290, m/n = 130634070942133969691 = 13*127*211*241*331*5171*909091
b=1155: n2290, m/n = 125619816774689521583 = 13*23*211*241*2161*8317*459691
b=1155: n2289, m/n = 4960197929509468992247 = 11*331*3851*590437*599144041
b=1155: n2289, m/n = 4650633632839026777571 = 11*241*8779*9091*24179*909091
b=1155: n2289, m/n = 1082086440281956979287 = 11*241*4093*24179*4124507971
b=1155: n2290, m/n = 389465717799003604121 = 11*211*2161*3851*20163494891
b=1155: n2290, m/n = 453746741819559644489 = 11*211*241*8779*101641*909091
b=1155: n2290, m/n = 454455472615483408201 = 11*23*127*2689*8779*599144041
b=1155: n2290, m/n = 413045856721840247477 = 11*13*241*331*8779*4124507971
b=1155: n2290, m/n = 135448002710508916571 = 11*13*127*241*4093*8317*909091
b=1155: n2290, m/n = 124889125248712362967 = 11*13*23*241*4093*5171*7444361
b=1155: n2289, m/n = 2586879096758707465693 = 11*11*8779*590437*4124507971
b=1155: n2290, m/n = 121578099877616787757 = 11*11*127*211*9091*4124507971
b=1155: n2291, m/n = 21862757336758123357 = 11*11*13*241*2689*5171*4147571
b=1155: n2291, m/n = 23576898873356367253 = 11*11*13*211*331*2689*8779*9091
b=1155: n2291, m/n = 12873788346368705899 = 11*11*13*23*3851*101641*909091
b=1155: n2288, m/n = 55668717888675589735891 = 7*463*3851*7444361*599144041
b=1155: n2288, m/n = 8318582422892154250957 = 7*331*2161*1661378260814161
b=1155: n2288, m/n = 24234694525647166589917 = 7*241*8779*9091*24179*7444361
b=1155: n2289, m/n = 1745061336284169814169 = 7*241*463*24179*101641*909091
b=1155: n2289, m/n = 5229457315609470352451 = 7*241*463*2161*5171*599144041
b=1155: n2288, m/n = 7867447262521524783637 = 7*211*331*463*8317*9091*459691
b=1155: n2288, m/n = 12059249720812863306983 = 7*127*241*8317*909091*7444361
b=1155: n2289, m/n = 6331494422822478058219 = 7*23*2161*2689*909091*7444361
b=1155: n2290, m/n = 251375547763779416677 = 7*23*127*211*331*4093*5171*8317
b=1155: n2289, m/n = 2309057960113107399287 = 7*13*23*463*8779*459691*590437
b=1155: n2290, m/n = 294757151198926798291 = 7*13*23*241*331*8317*8779*24179
b=1155: n2290, m/n = 187983078525757937653 = 7*11*2161*24179*101641*459691
b=1155: n2290, m/n = 312385922822701767809 = 7*11*241*3851*5171*8317*101641
b=1155: n2289, m/n = 959822552279898803573 = 7*11*211*2689*4093*9091*590437
b=1155: n2290, m/n = 135148844766167858087 = 7*11*211*241*2161*3851*4147571
b=1155: n2289, m/n = 3049614561298996883423 = 7*11*127*8317*9091*4124507971
b=1155: n2289, m/n = 729930835573336924373 = 7*11*127*211*590437*599144041
b=1155: n2290, m/n = 126749287437052268527 = 7*11*23*331*2161*2689*4093*9091
b=1155: n2291, m/n = 12629193562914557321 = 7*11*23*127*211*2689*4093*24179
b=1155: n2290, m/n = 329127490915871667019 = 7*11*13*23*463*4147571*7444361
b=1155: n2290, m/n = 146626864613174995049 = 7*11*13*23*331*4093*5171*909091
b=1155: n2291, m/n = 62360892120925158761 = 7*11*13*23*127*5171*4124507971
b=1155: n2291, m/n = 43049871118696679237 = 7*11*13*23*127*3851*8317*459691
b=1155: n2290, m/n = 211118031816652303651 = 7*11*11*4093*101641*599144041
b=1155: n2290, m/n = 434492319834779705807 = 7*11*11*4093*8779*24179*590437
b=1155: n2291, m/n = 38730472651510357333 = 7*11*11*211*2161*24179*4147571
b=1155: n2292, m/n = 5125320638332083343 = 7*11*11*23*211*241*463*2161*5171
b=1155: n2290, m/n = 171745366114388079013 = 7*11*11*13*331*8779*9091*590437
b=1155: n2287, m/n = 15263888980305215407409 = 7*7*211*331*7444361*599144041
b=1155: n2289, m/n = 189950507422560662099 = 7*7*23*127*241*331*463*4093*8779
b=1155: n2290, m/n = 65234258608952437249 = 7*7*23*127*211*241*2161*4147571
b=1155: n2289, m/n = 111323941182748009807 = 7*7*13*127*2689*4093*5171*24179
b=1155: n2289, m/n = 191204887538137257967 = 7*7*13*127*211*2161*8779*590437
b=1155: n2289, m/n = 372257671572268347047 = 7*7*13*23*2161*3851*5171*590437
b=1155: n2289, m/n = 148619115337035698173 = 7*7*13*23*241*463*2689*3851*8779
b=1155: n2289, m/n = 187634493576065596333 = 7*7*13*23*211*463*3851*4093*8317
b=1155: n2290, m/n = 44692031120235340933 = 7*7*13*23*127*2161*24179*459691
b=1155: n2289, m/n = 264778187986065752089 = 7*7*13*23*127*463*3851*8779*9091
b=1155: n2290, m/n = 14689131054352221649 = 7*7*13*23*127*241*331*4093*24179
b=1155: n2289, m/n = 647118355005220763819 = 7*7*11*127*5171*8317*9091*24179
b=1155: n2291, m/n = 2818398130617710641 = 7*7*11*13*23*127*331*4093*101641
b=1155: n2289, m/n = 160404329489067208853 = 7*7*11*11*463*4093*24179*590437
b=1155: n2290, m/n = 29131211352465225157 = 7*7*11*11*211*241*2689*4093*8779
b=1155: n2290, m/n = 27819533337224746733 = 7*7*11*11*23*241*3851*9091*24179
b=1155: n2291, m/n = 4134136854368614093 = 7*7*11*11*13*127*331*2161*590437
b=1530: n3039, m/n = 3526356886130595233281 = 1021*6121*4188901*134703241
b=1530: n3038, m/n = 7459296852085490399641 = 181*302941*855781*158963941
b=1530: n3038, m/n = 13595396867010956667289 = 181*409*3541*6121*9901*855781
b=1530: n3039, m/n = 1490097839206090109741 = 101*1021*9181*9901*158963941
b=1530: n3038, m/n = 9996208229622114423881 = 101*409*9901*855781*28559389
b=1530: n3039, m/n = 3482050889572036524629 = 101*409*3061*9181*9901*302941
b=1530: n3038, m/n = 5298131927451141611641 = 61*181*3061*6121*9901*2586721

***