Triangle Of The Gods
November 10, 2015
The nth element of the Smarandache consecutive number sequence (A007908) is the sequence of the numbers from 1 to n concatenated in order:
1, 12, 123, 1234, 12345, 123456, 1234567, 12345678, 123456789, 12345678910, 1234567891011, 123456789101112, …
The sequence is sometimes called the “Triangle of the Gods,” and the story goes that anyone who can specify the smallest prime number in the sequence is admitted to heaven.
Your task is to find the smallest prime number in the sequence. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
Ok, I’ll be the first one to admit I got trolled :P
Sequence generator:
Scala:
1. stream of Smarandache numbers
2. stream of primes
3. take te common elements
def sqrt(number: BigInt) = { val one = BigInt(1) def next(n: BigInt, i: BigInt): BigInt = (n + i / n) >> 1 var n = one var n1 = next(n, number) while ((n1 - n).abs > one) { n = n1 n1 = next(n, number) } while (n1 * n1 > number) { n1 -= one } n1 } //> sqrt: (number: BigInt)BigInt def smarandacheBI(n: BigInt = 1): Stream[BigInt] = { if (n % 2 == 0 || n % 5 == 0) smarandacheBI(n + 1) else { val akt = (for (s <- BigInt(1) to n) yield s.toString()).reduce(_ + _) if(akt.map(_.toInt).sum % 3==0) smarandacheBI(n + 1) else { println(akt) Stream.cons(BigInt(akt), smarandacheBI(n + BigInt(1))) } } } //> smarandacheBI: (n: BigInt)Stream[BigInt] def isPrimeBI(n: BigInt, d: BigInt = BigInt(2)): Boolean = { //println(n+" "+d) if (n == 1) false else if (d >= sqrt(n)) true else if (n % d == 0) false else isPrimeBI(n, d + 1) } //> isPrimeBI: (n: BigInt, d: BigInt)Boolean smarandacheBI().filter(isPrimeBI(_)).take(1).toListActually, I’ve had more fun factoring elements of the Smarandache sequence than searching for primes:
Funny that these days I think of writing a generator function first. I could’ve just included that logic in the loop. I blame all the playing around with ranges (i.e. lazy sequences) that I’ve been doing.
I reused the isprime function (not shown) that I’d written for an earlier collatz primes exercise.
#include <sstream> #include <string> #include <algorithm> #include <iterator> #include <iostream> #include <boost/multiprecision/cpp_int.hpp> #include "isprime.hpp" using Int = boost::multiprecision::cpp_int; auto triangle = [current = Int(1), oss = std::ostringstream()]() mutable { oss << current++; return Int(oss.str()); }; int main() { while (true) { Int candidate = triangle(); bool prime = isprime(candidate); std::cout << candidate << ": " << prime << '\n'; if (prime) break; } }