Triangles of the Gods, Solution Ideas

This problem has generated quite a bit of attention. Please enjoy the comments.

Triangles of the Gods



An angel descends to Earth and shows the following simple progression of numbers:
1
12
123
1234
12345
123456
1234567
12345678
... etc.

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?
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?

Some Mind-Numbing Answers -- I Welcome More Findings

From: "Daniel Dockery" 

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."

More Ideas

From: David Jones Before we get going too far, the triangle is still not well defined. What is sequence after 123456789? Depending on the pattern you want, it could be
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 wrote:

>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.

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

// 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.