An angel descends to Earth and shows the following simple progression of numbers:
1
12
123
1234
12345
123456
1234567
12345678
... etc.
This problem has generated quite a bit of attention. Please enjoy the comments.
1) What is the first and second prime number we encounter on this triangle?2)
What percentage of prime numbers do you expect as we scan more rows in
the mysterious triangle?3) If you could add one digit
to the beginning of each number in order to increase the number of primes,
what would it be? Justify your answer.4) If you could
add one digit to the end of each number in order to increase the number
of primes, what would it be? Justify your answer.5)
What is the largest prime number in this progression known to humanity?6)
You get to ask the angel a fascinating question about this triangle. What
is your question? (You get extra points if you can give a good answer to
your new question. Be creative.)
What can you add to our findings?
Greetings,
Query: for generating this, do we continue to add the natural numbers
in sequence, or, considering the later references to prefixing or suffixing
only single digits, do we only add the sequence of digits 1 through 0?
E.g., would this continue
123456789 12345678910 1234567891011 123456789101112 12345678910111213 ... etc. or 123456789 1234567890 12345678901 123456789012 1234567890123 ... etc. ? Since I am unsure, I'll give responses for both, below. For convenience of reference, I'll refer to the first as the "natural" sequence, and the second as the "digit" sequence. > The angel will let you enter the afterlife if you can address > 2 or more of the questions below in a satisfactory manner: > > 1) What is the first and second prime number we encounter on this > triangle? In the natural sequence, I found no prime numbers in the first five hundred rows... Here are some primes I did find, with "0" in the digit string: Row 171: 123456789012345678901234567890 \ 123456789012345678901234567890 \ 123456789012345678901234567890 \ 123456789012345678901234567890 \ 123456789012345678901234567890 \ 123456789012345678901 Row 277: 123456789012345678901234567890 \ 123456789012345678901234567890 \ 123456789012345678901234567890 \ 123456789012345678901234567890 \ 123456789012345678901234567890 \ 123456789012345678901234567890 \ 123456789012345678901234567890 \ 123456789012345678901234567890 \ 123456789012345678901234567890 \ 1234567 Row 367: 123456789012345678901234567890 \ 123456789012345678901234567890 \ 123456789012345678901234567890 \ 123456789012345678901234567890 \ 123456789012345678901234567890 \ 123456789012345678901234567890 \ 123456789012345678901234567890 \ 123456789012345678901234567890 \ 123456789012345678901234567890 \ 123456789012345678901234567890 \ 123456789012345678901234567890 \ 123456789012345678901234567890 \ 1234567 Row 561: 123456789012345678901234567890 \ 123456789012345678901234567890 \ 123456789012345678901234567890 \ 123456789012345678901234567890 \ 123456789012345678901234567890 \ 123456789012345678901234567890 \ 123456789012345678901234567890 \ 123456789012345678901234567890 \ 123456789012345678901234567890 \ 123456789012345678901234567890 \ 123456789012345678901234567890 \ 123456789012345678901234567890 \ 123456789012345678901234567890 \ 123456789012345678901234567890 \ 123456789012345678901234567890 \ 123456789012345678901234567890 \ 123456789012345678901234567890 \ 123456789012345678901234567890 \ 123456789012345678901 Row 567: 123456789012345678901234567890 \ 123456789012345678901234567890 \ 123456789012345678901234567890 \ 123456789012345678901234567890 \ 123456789012345678901234567890 \ 123456789012345678901234567890 \ 123456789012345678901234567890 \ 123456789012345678901234567890 \ 123456789012345678901234567890 \ 123456789012345678901234567890 \ 123456789012345678901234567890 \ 123456789012345678901234567890 \ 123456789012345678901234567890 \ 123456789012345678901234567890 \ 123456789012345678901234567890 \ 123456789012345678901234567890 \ 123456789012345678901234567890 \ 123456789012345678901234567890 \ 123456789012345678901234567 I found no others in the first 1000 rows of the digit sequence. > 3) If you could add one digit to the beginning of each number in > order to increase the number of primes, what would it be? Justify > your answer. Searching the first two hundred rows of the natural sequence, all digits 1 through 9 except for 5, 6 and 9 produced two primes when prefixed to the rows of the sequence. Six and nine produced one each, and I found none for 5 in this range. For reference, here are the rows and numbers which were prime for the given digits: Prefixing 1: Row 1: 11 Row 3: 1123 Prefixing 2: Row 21: 2123456789101112131415161718192021 Row 69: 2123456789101112131415161718192021 \ 2223242526272829303132333435363738 \ 3940414243444546474849505152535455 \ 5657585960616263646566676869 Prefixing 3: Row 1: 31 Row 19: 312345678910111213141516171819 Prefixing 4: Row 1: 41 Row 17: 41234567891011121314151617 Prefixing 6: Row 1: 61 Prefixing 7: Row 1: 71 Row 7: 71234567 Row 183: 712345678910111213141516171819202122 \ 232425262728293031323334353637383940 \ 414243444546474849505152535455565758 \ 596061626364656667686970717273747576 \ 777879808182838485868788899091929394 \ 9596979899100101102103104105106107108 \ 109110111112113114115116117118119120 \ 121122123124125126127128129130131132 \ 133134135136137138139140141142143144 \ 145146147148149150151152153154155156 \ 157158159160161162163164165166167168 \ 169170171172173174175176177178179180 \ 181182183 Prefixing 8: Row 3: 8123 Row 39: 812345678910111213141516171819202122 \ 2324252627282930313233343536373839 Prefixing 9: Row 13: 912345678910111213 For the first two hundred rows of the digital sequence, prefixing 4 produced the most with 4 primes; 1, 6 and 7 each produced three primes; 3 and 5 each produced two; and 8 and 9 produced one each. Prefixing 1: Row 1: 11 Row 3: 1123 Row 161: 1123456789012345678901234567890123456 \ 7890123456789012345678901234567890123 \ 4567890123456789012345678901234567890 \ 1234567890123456789012345678901234567 \ 89012345678901 Prefixing 3: Row 1: 31 Row 11: 312345678901 Prefixing 4: Row 1: 41 Row 17: 412345678901234567 Row 31: 41234567890123456789012345678901 Row 99: 4123456789012345678901234567890123456 \ 7890123456789012345678901234567890123 \ 45678901234567890123456789 Prefixing 5: Row 49: 5123456789012345678901234567890123456 \ 7890123456789 Row 59: 5123456789012345678901234567890123456 \ 78901234567890123456789 Prefixing 6: Row 1: 61 Row 41: 6123456789012345678901234567890123456 \ 78901 Row 71: 6123456789012345678901234567890123456 \ 78901234567890123456789012345678901 Prefixing 7: Row 1: 71 Row 7: 71234567 Row 19: 71234567890123456789 Prefixing 8: Row 3: 8123 Prefixing 9: Row 21: 9123456789012345678901 > 4) If you could add one digit to the end of each number in > order to increase the number of primes, what would it be? > Justify your answer. From the first two hundred rows of the natural sequence, it would seem that attaching a 1 or a 7 would generate the most: adding 1 as a suffix produces 7 primes, adding 7 produces 8; adding 3 or 9 both produced three each. 1: Row 1: 11 Row 3: 1231 Row 9: 1234567891 Row 11: 12345678910111 Row 16: 123456789101112131415161 Row 26: 1234567891011121314151617181920212223 \ 2425261 Row 114: 1234567891011121314151617181920212223 \ 24252627282930313233343536373839404142 \ 43444546474849505152535455565758596061 \ 62636465666768697071727374757677787980 \ 81828384858687888990919293949596979899 \ 100101102103104105106107108109110111112\ 1131141 3: Row 1: 13 Row 4: 12343 Row 97: 123456789101112131415161718192021222324\ 25262728293031323334353637383940414243 \ 44454647484950515253545556575859606162 \ 63646566676869707172737475767778798081 \ 828384858687888990919293949596973 7: Row 1: 17 Row 2: 127 Row 3: 1237 Row 4: 12347 Row 5: 123457 Row 21: 1234567891011121314151617181920217 Row 28: 123456789101112131415161718192021222324\ 252627287 Row 107: 123456789101112131415161718192021222324\ 25262728293031323334353637383940414243 \ 44454647484950515253545556575859606162 \ 63646566676869707172737475767778798081 \ 828384858687888990919293949596979899100\ 1011021031041051061077 9: Row 1: 19 Row 16: 123456789101112131415169 Row 22: 123456789101112131415161718192021229 I found it curious that the first five rows all became prime when attaching the digit 7. For the digit sequence, the number of primes remains rather close to the same: 1 now produces eight primes, one more than in the natural sequence, and 9 now produces only two, one less than in the natural sequence; 3 and 7 still produce the same number of primes as in the natural sequence (3 and 8 respectively). 1: Row 1: 11 Row 3: 1231 Row 9: 1234567891 Row 11: 123456789011 Row 17: 123456789012345671 Row 19: 12345678901234567891 Row 33: 1234567890123456789012345678901231 Row 170: 1234567890123456789012345678901234567890 \ 1234567890123456789012345678901234567890 \ 1234567890123456789012345678901234567890 \ 1234567890123456789012345678901234567890 \ 12345678901 3: Row 1: 13 Row 4: 12343 Row 104: 1234567890123456789012345678901234567890 \ 1234567890123456789012345678901234567890 \ 1234567890123456789012343 7: Row 1: 17 Row 2: 127 Row 3: 1237 Row 4: 12347 Row 5: 123457 Row 41: 1234567890123456789012345678901234567890 \ 17 Row 54: 1234567890123456789012345678901234567890 \ 123456789012347 Row 91: 1234567890123456789012345678901234567890 \ 1234567890123456789012345678901234567890 \ 123456789017 9: Row 1: 19 Row 54: 1234567890123456789012345678901234567890 \ 123456789012349 > 5) What is the largest prime number in this progression known > to humanity? With regard to the natural sequence, I'm not certain, but it would have to be greater than 123456789101112131415161718192021222324252627 \ 2829303132333435363738394041424344454647484950\ 5152535455565758596061626364656667686970717273\ 7475767778798081828384858687888990919293949596\ 979899100101102103104105106107108109110111112 \ 113114115116117118119120121122123124125126127 \ 128129130131132133134135136137138139140141142 \ 143144145146147148149150151152153154155156157 \ 158159160161162163164165166167168169170171172 \ 173174175176177178179180181182183184185186187 \ 188189190191192193194195196197198199200201202 \ 203204205206207208209210211212213214215216217 \ 218219220221222223224225226227228229230231232 \ 233234235236237238239240241242243244245246247 \ 248249250251252253254255256257258259260261262 \ 263264265266267268269270271272273274275276277 \ 278279280281282283284285286287288289290291292 \ 293294295296297298299300301302303304305306307 \ 308309310311312313314315316317318319320321322 \ 323324325326327328329330331332333334335336337 \ 338339340341342343344345346347348349350351352 \ 353354355356357358359360361362363364365366367 \ 368369370371372373374375376377378379380381382 \ 383384385386387388389390391392393394395396397 \ 398399400401402403404405406407408409410411412 \ 413414415416417418419420421422423424425426427 \ 428429430431432433434435436437438439440441442 \ 443444445446447448449450451452453454455456457 \ 458459460461462463464465466467468469470471472 \ 473474475476477478479480481482483484485486487 \ 488489490491492493494495496497498499500 For the digit sequence, unless someone has found one larger, it would be Row 567: 123456789012345678901234567890 \ 123456789012345678901234567890 \ 123456789012345678901234567890 \ 123456789012345678901234567890 \ 123456789012345678901234567890 \ 123456789012345678901234567890 \ 123456789012345678901234567890 \ 123456789012345678901234567890 \ 123456789012345678901234567890 \ 123456789012345678901234567890 \ 123456789012345678901234567890 \ 123456789012345678901234567890 \ 123456789012345678901234567890 \ 123456789012345678901234567890 \ 123456789012345678901234567890 \ 123456789012345678901234567890 \ 123456789012345678901234567890 \ 123456789012345678901234567890 \ 123456789012345678901234567 The next would have to be beyond row 1000, and greater than 1234567890123456789012345678901234567890 \ 1234567890123456789012345678901234567890 \ 1234567890123456789012345678901234567890 \ 1234567890123456789012345678901234567890 \ 1234567890123456789012345678901234567890 \ 1234567890123456789012345678901234567890 \ 1234567890123456789012345678901234567890 \ 1234567890123456789012345678901234567890 \ 1234567890123456789012345678901234567890 \ 1234567890123456789012345678901234567890 \ 1234567890123456789012345678901234567890 \ 1234567890123456789012345678901234567890 \ 1234567890123456789012345678901234567890 \ 1234567890123456789012345678901234567890 \ 1234567890123456789012345678901234567890 \ 1234567890123456789012345678901234567890 \ 1234567890123456789012345678901234567890 \ 1234567890123456789012345678901234567890 \ 1234567890123456789012345678901234567890 \ 1234567890123456789012345678901234567890 \ 1234567890123456789012345678901234567890 \ 1234567890123456789012345678901234567890 \ 1234567890123456789012345678901234567890 \ 1234567890123456789012345678901234567890 \ 1234567890123456789012345678901234567890 --Daniel
Cliff says, "Daniel you are amazing."
a) 1234567890, 12345678901, 123456789012 b) 1234567891, 12345678912, 123456789123 c) 12345678910, 1234567891011, 123456789101112 > 1) What is the first and second prime number we encounter on this > triangle? > 2) What percentage of prime numbers do you expect as we > scan more rows in the mysterious triangle?Well, off the top, there are ton of number we can skim off. Obviously the ones ending in even numbers or 5 can go. It also turns out that an abnormally high about of these numbers are divisible by 3. For example, look at sequence b. Not only does every number ending in 3, 6 or 9 get knocked out (sum of the digits is divisible by 3) but the number preceeding in does also (if we subtract a multiple of three, which the last digit is, we still have a number divisible by three). So in sequences a and c, 2/3rds of the numbers can be immediately removed via divisibility by three. Sequence b gives us 6/10ths removal. By the time you combine all of these together, Sequences a & b can only be prime when the final digit ends in 1 or 7. Sequence c is a little trickier but I think you can still whittle it down to about 20% of the candidates. After this, I think you have to get into some more complicated tricks.
> 3) If you could add one digit to the beginning of each number in > order to increase the number of primes, what would it be? Justify > your answer.This is tricky. Adding such a number does not really change anything above other than shifting our divisibility by three trick. As it is, three REALLY eliminates all numbers except those that end in 1, 4, and 7. But 4 is even so we can kill that. By adding a number in front, we can change those candidates into 2, 5, and 8 (by, say, adding two) or 3, 6, and 9 (by, say, adding one). Obviously shifting to 2, 5, and 8 means that NONE of the numbers could be prime. Shifting to 3, 6, and 9 is no better (or worse) than 1, 4, 7. Without deeper study I can't make a claim that any number would increase the number of primes, but I can certainly decrease them for you. Again though, this idea only applies to sequences a and b.
> 4) If you could add one digit to the end of each number in > order to increase the number of primes, what would it be? > Justify your answer.Other than ading 2,4,6,8,0,5 is obviously bad, I can't yet show that any one of 1,3,7,9 is any better or worse than the others.
> 5) What is the largest prime number in this progression known > to humanity?pass Davy Other comments:
> An angel descends to Earth and shows the following simple progression >of numbers: > >1 >12 >123 >1234 >12345 >123456 >1234567 >12345678 >... etc.There are several possible continuations of this sequence. The next is obviously 123456789, but after that do you continue 1234567890 or 12345678910?
>The angel will let you enter the afterlife if you can address 2 or more >of the questions below in a satisfactory manner: >1) What is the first and second prime number we encounter on this >triangle? Assuming the answer to my question is 1234567890, they are 123456789012345678901234567890123456789012345678901234567890123456789 012345678901234567890123456789012345678901234567890123456789012345678 901234567890123456789012345678901 and 123456789012345678901234567890123456789012345678901234567890123456789 012345678901234567890123456789012345678901234567890123456789012345678 901234567890123456789012345678901234567890123456789012345678901234567 8901234567890123456789012345678901234567890123456789012345678901234567 (the numbers with 171 and 277 digits) >2) What percentage of prime numbers do you expect as we scan more rows >in the mysterious triangle? Almost certainly 0 (asymptotically), although there should be infinitely many primes in the sequence. >3) If you could add one digit to the beginning of each number in order >to increase the number of primes, what would it be? Justify your answer. Either 1, 4 or 7. 7 out of every 10 of the numbers are divisible by 3, the other 3 out of 10 are congruent to 1 mod 3. If you add 1, 4 or 7 at the beginning, none will be divisible by 3. >4) If you could add one digit to the end of each number in order to >increase the number of primes, what would it be? Justify your answer. Either 1 or 7, for the same reason as (3) (of course adding a 4 at the end would be a bad idea...) Robert Israel israel@math.ubc.ca Department of Mathematics Other comments: >There are several possible continuations of this sequence. The next is >obviously 123456789, but after that do you continue 1234567890 or >12345678910? I'd personally say that 1234567900 is next, using the recursion f(1) = 1 f(n) = 10 f(n-1) + n for n > 1. or f(n) = sum(m=1 to n) m*10^(n-m) or f(n) = (10^(n+1) - 10 - 9n) / 81 -- ------------------------ Mark Jeffrey Tilford tilford@ugcs.caltech.edu
Mark Ganson: I also posted to the USENET a response to your Triangle
of the Gods puzzle. I have now tested up to and including natural sequence
number 1144 (even number) without finding any primes. 1144) 123...114211431144.
I'm testing with Java using the BigIntegers. It's really a very short and
sweet source code file. Let me know if you want to see it.
Mark Ganson: To the Triangle puzzle, I am attaching my Java source code.
Feel free to use it however you like. It is very elementary, so I feel
no need to attach any copyright to it. It works with the Java BigInteger
class, which does most of the work for us. The method BigInteger.isProbablePrime(32)
tests that particular BigInteger for primeness/compositeness. It is called
isProbablePrime() because it is a probability test. If the result is that
the number is composite, you can be assured that the number is composite.
So, for our purposes, since all the numbers tested were found to be composite,
we can be assured that all of the numbers in the triangle (up to row 1534)
were all composite. If the result is that the number in question is probably
prime, there is still a chance that it might be composite. The chances,
when using 32 as the parameter, however, are very small. It is somewhere
in the neighborhood of ((2¬32)-1)/2¬32. Or, stated another way,
the chances that a number that is tested prime is really composite are
1 in 2¬32.
The source code (TrianglePuzzle.java) contains some comments on how
to use it. It also has a block of code that has been commented out. The
commented out code can be uncommented if you want the program to pick up
from where I left off (at row 1534). You may, in your discretion, remove
all the comments and/or commented out code for your publication. You may
make any other changes you deem proper to the code, also, of course. If
you do decide to print the code, I'd appreciate a complimentary copy of
the book, if that is not too much to ask. Thanks, Mark Ganson
Mark Ganson >I visited your webpage and reviewed some of the other responses. I
>see no justification for continuing the sequence in any way other
>than:
>9) 123456789
>10) 12345678910
>11) 1234567891011
>...
Under this interpretation, the n'th member of the sequence has on the order
of n log n digits (rather than n digits for other interpretations), and
therefore "probability" on the order of 1/(n log n) of being prime. Now
sum_n 1/(n log n) does diverge, but very very slowly. So I'd guess there
would be infinitely many primes in the sequence, but they'll be very scarce.
Given that you're up to number 743 and haven't found one, it may be unlikely
that one will be found in our lifetimes.
Robert Israel israel@math.ubc.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia
Vancouver, BC, Canada V6T 1Z2
tjwojo@hotmail.com (Todd Wojtalewski): Of course, since there are no digits
greater than 8 shown, it cannot be assumed from the information given that
the numbers are base 10. Perhaps the sequence goes as such:
123456789ABCDEF.....
or
12345678012345678...
However, these numbers will not have values unless a base system is determined.
This dilemma is the equivalent of purgatory: the victim must go through
a period of hell and painful tribulations in order to achieve the deserved
eternal bliss.
// This program will build the triangle of numbers and test each number for
// primeness or compositeness. The first 14 numbers will be displayed to
// the standard output device (typically the display monitor). The program
// finishes when the first 2 primes are encountered. These 2 primes are
// displayed to the standard output device and the program then exits.
//
// To prevent the found primes from streaming by after hours and hours of
// processing, use this command line to execute the program:
//
// java TrianglePuzzle >logfile.txt
//
// This will redirect all standard output to a file named logfile.txt. The
// output to the standard error device (the display monitor) will still be
// displayed to the monitor so you can still monitor the program's progress.
//
// CTRL + C will halt the program at any time.
import java.math.*;
import java.util.*;
import java.lang.Math;
public final class TrianglePuzzle {
static BigInteger n1 = new BigInteger("1");
static BigInteger n15 = new BigInteger("15");
public static void main(String args[]){
BigInteger nII = n1; //nII will be our counter
BigInteger nTri = n1; //Triangle row
StringBuffer sbTri = new StringBuffer(nII.toString());
BigInteger nFirstPrime = n1;
BigInteger nSecondPrime = n1;
boolean bFirstPrimeFound = false;
boolean bSecondPrimeFound = false;
/* //uncomment this block of code and recompile to start from where I left
off
//at row number 1534
for (int ii = 2; ii <= 1534; ii++){
sbTri.append(new Integer(ii).toString());
}
nII = new BigInteger("1534");
*/
System.out.println(nII.toString()+") "+sbTri.toString());
while (!bFirstPrimeFound && !bSecondPrimeFound){
nII = nII.add(n1); //increment nII
sbTri = sbTri.append(nII.toString());
nTri = new BigInteger(sbTri.toString());
if (nTri.isProbablePrime(32)){
if (!bFirstPrimeFound){
nFirstPrime = nTri;
bFirstPrimeFound = true;
System.out.println("1st prime is: "+nII.toString()+") "+
nFirstPrime.toString());
System.out.println();
System.err.println("1st prime is: "+nII.toString()+") "+
nFirstPrime.toString());
System.err.println();
} else if (!bSecondPrimeFound){
nSecondPrime = nTri;
bSecondPrimeFound = true;
System.out.println("2nd prime is: "+nII.toString()+") "+
nSecondPrime.toString());
System.err.println("2nd prime is: "+nII.toString()+") "+
nSecondPrime.toString());
}
}
if (nII.compareTo(n15) == -1){ //display first 14 numbers in the triangle
System.out.println(nII.toString()+") "+nTri.toString());
} else { //beyond first 15, just show which row we're on out to the
console
System.err.println(nII.toString());
}
}
}
}
Return to
Cliff Pickover's home page which includes computer art, educational
puzzles, higher dimensions, fractals, virtual caverns, JAVA/VRML, alien
creatures, black hole artwork, and animations. Click here
for a complete list of over 20 Cliff Pickover books.