[math-fun] Number Theory 101
The smallest decimal-digits prime composed of the concatenation of 7 distinct decimal-digit primes is 1113257317, composed of 11, 13, 2, 5, 7, 3, and 17. What are the first three digits of the smallest decimal- digits prime composed of the concatenation of 26 distinct decimal- digit primes? (Bonus marks: Allowing probable primes, what is the entire number?)
Attempted spoiler: The first 26 primes go up to 101, so it seems like a good bet that this number would start with 101. There are 25! choices for the remaining bunch of digits and it sure seems likely that one of them would be prime. Hm, unless there's something like the digit sum divisible by 3 that makes it impossible. Let's see. 2+3+5+7+11+13+17+19+23+29+ 31+37+41+43+47+53+59+61+67+71+ 73+79+83+89+97+101 = 1161 so it is indeed divisible by 3. OK, then, how about 103 in place of the 101? (It seems clear that we want to keep the number of digits smaller by having only one three-digit prime and using all the first 25 primes). I'll conjecture 103, and not feed the 25! possibilities into a probable-prime test to see which one(s) are prime. I'm betting a lot of them are and I could probably have a solution to this within a short bit of computer time. --Joshua On Tue, Aug 3, 2010 at 9:37 AM, Hans Havermann <pxp@rogers.com> wrote:
The smallest decimal-digits prime composed of the concatenation of 7 distinct decimal-digit primes is 1113257317, composed of 11, 13, 2, 5, 7, 3, and 17. What are the first three digits of the smallest decimal-digits prime composed of the concatenation of 26 distinct decimal-digit primes? (Bonus marks: Allowing probable primes, what is the entire number?)
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
We can't use 2, 3, ..., 101 because it'd be divisible by 3. So we use 2, 3, ..., 97 and 103. The first three digits are very likely 103 because we can expect that some permutation of the remaining primes will make it prime. Let x be the concatenation of 103, 11, 13, 17, 19, 2, 23, 29,31, 3, 37, 41, 43, 47, 53, 5, 59, 61, 67, 71, 73, 7. The smallest candidates and their smallest divisors are: x79838997, 19 x79839789, 17 x79898397, 29 x79899783, 21773 x79978389, 43 x79978983, 53 x83798997, 1664337338519 x83799789, 149 x83897997, 479 x83899779, 36767 x83977989, 7 x83978979, 97 x89798397, 59 x89799783, 17 x89837997, 7 x89839779, 7057327 x89977983, 7 x89978379, 7283 x97798389, 23 x97798983 is prime!!! We can prove the primality of 1031113171922329313374143475355961677173797798983 by using the fact that 5 is its (smallest) primitive root and 1031113171922329313374143475355961677173797798983 - 1 = 2 * 48866600953 * 74195778089023 * 142195225375699804440389. Hope this answer would make me pass Number Theory 101. :) Warut On Tue, Aug 3, 2010 at 11:37 PM, Hans Havermann <pxp@rogers.com> wrote:
The smallest decimal-digits prime composed of the concatenation of 7 distinct decimal-digit primes is 1113257317, composed of 11, 13, 2, 5, 7, 3, and 17. What are the first three digits of the smallest decimal-digits prime composed of the concatenation of 26 distinct decimal-digit primes? (Bonus marks: Allowing probable primes, what is the entire number?)
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Warut Roonguthai:
We can prove the primality of 1031113171922329313374143475355961677173797798983
That didn't take long. :) I would appreciate being notified of any errors in this compilation of solutions up to 120 distinct concatenated primes: http://chesswanks.com/seq/b083427.txt The entries from n = 26 on all rely on the assumption that the n smallest primes are concatenated, unless the resulting number is divisible by 3, in which case the n-th prime is replaced with the first available larger prime resulting in a concatenated number not divisible by 3. I trust that this method will fail as we further approach n = 168, and then work again in the digit-regime change starting at n = 169.
I found that one could get the (probable prime) solution for n=168 by removing 67, 71, 79, 83, 7, 97, 73, 89 from the least significant digits of the solution for n=120, and then concatenating 661, 673, 67, 677, 683, 691, 701, 709, 71, 719, 727, 733, 73, 739, 743, 751, 757, 761, 769, 773, 7, 787, 797, 79, 809, 811, 821, 823, 827, 829, 83, 839, 853, 857, 859, 863, 877, 881, 883, 887, 89, 907, 911, 919, 929, 937, 941, 947, 953, 967, 977, 991, 983, 97, 997, 971. Warut On Wed, Aug 4, 2010 at 2:46 AM, Hans Havermann <pxp@rogers.com> wrote:
I would appreciate being notified of any errors in this compilation of solutions up to 120 distinct concatenated primes:
http://chesswanks.com/seq/b083427.txt
The entries from n = 26 on all rely on the assumption that the n smallest primes are concatenated, unless the resulting number is divisible by 3, in which case the n-th prime is replaced with the first available larger prime resulting in a concatenated number not divisible by 3. I trust that this method will fail as we further approach n = 168, and then work again in the digit-regime change starting at n = 169.
participants (3)
-
Hans Havermann -
Joshua Zucker -
Warut Roonguthai