| ' Puzzlet #095 ' 67 is a Prime Number with consecutively ' increasing digits. So is 4567. Find any others ' using only the digits 1 - 9 inclusive. ' By Dave Ellis. declare IsPrime(p: int) def it1, it2, nr: int def nr$: string openconsole color 11, 0: cls print "Searching ...": print color 14, 0 for it1 = 1 to 8 nr$ = ltrim$(str$(it1)) for it2 = it1 + 1 to 9 nr$ = nr$ + ltrim$(str$(it2)) nr = val(nr$) if IsPrime(nr) print using (string$(12, "#"), nr) endif next it2 next it1 color 11, 0 print: print "That's all!!" print: print " Press a key ... ", do: until inkey$ <> "" closeconsole end sub IsPrime(p) ' if p is prime, returns -1, ' otherwise returns 0 def flag, i, root: int if p = 2 | p = 3 flag = -1 else if p % 2 = 0 | p < 2 flag = 0 else root = sqrt(p) i = 3 flag = -1 do if p % i = 0 flag = 0 else i = i + 2 endif until flag = 0 | i > root endif endif return flag |
| PROGRAM NOTES To help explain how the above code works, I've assigned line numbers to the part that does all the work, as shown below. |
| 1 2 3 4 5 6 7 8 9 10 |
|
for it1 = 1 to 8 nr$ = ltrim$(str$(it1)) for it2 = it1 + 1 to 9 nr$ = nr$ + ltrim$(str$(it2)) nr = val(nr$) if IsPrime(nr) print using (string$(12, "#"), nr) endif next it2 next it1 |
| Now let's do an exegesis of the code, based on the above line numbers: |
| 1 |
for it1 = 1 to 8. Variable it1 holds the first digit of any solution. Since the answer must be at least two digits long, and they must be in ascending order, it1 cannot be greater than 8, so its range is 1 to 8. |
| 2 |
nr$ = ltrim$(str$(it1)). In order to manipulate it1 it will need to be in string form. Line 2 converts it to a string and saves the result in nr$. |
| 3 |
for it2 = it1 + 1 to 9. The second digit in the solution, that is, the one after it1, must always be one greater than it1. That digit will be assigned using variable it2, and its range therefore is it1 + 1 to a maximum of 9. |
| 4 |
nr$ = nr$ + ltrim$(str$(it2)). The current value of it2 is converted into a string and concatenated onto the end of nr$, the result being saved back into nr$ itself. This concatenation is the reason for turning it1 into a string in line 2. So at this stage, if it1 had been 3 and it2 4, then nr$ would hold "34". |
| 5 |
nr = val(nr$). We need to check if nr$ is holding a prime number, and we employ function IsPrime[] to do that. IsPrime() needs an integer as its argument, so nr$ is converted to the integer form and saved in nr ready to pass to IsPrime(). |
| 6 |
if IsPrime(nr). nr is passed as
parameter to IsPrime(). If nr contains a prime number, TRUE
(-1) is returned, otherwise FALSE (0). |
| 7 |
print using (string$(12, "#"), nr). If IsPrime() returns TRUE, we have a valid solution, and it's printed out to the computer screen. |
| 8 |
endif. Housekeeping - closes the IF-ENDIF clause opened in line 6. |
| 9 |
next it2. Housekeeping - completes the (inner) FOR-NEXT loop opened in line 3. |
| 10 |
next it1. Housekeeping - completes the (outer) FOR-NEXT loop opened in line 1. |
| Note
that, after the first iteration of the inner FOR-NEXT loop, it2 keeps adding bits onto the end
of nr$. The overall effect is
the generation of the complete set in the order given: 12, 123, 1234, 12345,
123456, 1234567, 12345678, 123456789.
23, 234, 2345, 23456, 234567, 2345678, 23456789. 34, 345, 3456, 34567, 345678, 3456789. 45, 456, 4567, 45678, 456789. 56, 567, 5678, 56789. 67, 678, 6789. 78, 789. 89. This is a lot quicker than generating every possible 5-digit palindrome, with limiting algorithms built in to ensure only wave palindromes are included. |
| When
you run the program, you'll see the inset results printed out onto your
computer's screen. These are the only solutions. They're mostly uninteresting, but the second one comes tantalisingly close to a perfect 123456789. |
|
Searching
... 23 23456789 4567 67 89 That's all! Press a key ... |