Smarandache-Wellin primes
A Smarandache-Wellin number (S-W number for short) is an integer that in a given base is the concatenation of the first n prime numbers written in that base. A base of 10 will be assumed for this task.
Smarandache-Wellin primes is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
- Definitions
A Derived S-W number (not an 'official' term) is an integer formed from a S-W number by working out the number of times each of the digits 0 to 9 occurs in that number, concatenating those frequencies in the same order (i.e. frequency of '0' first, frequency of '1' second etc) and removing any leading zeros.
- Examples
'23571113' is the sixth S-W number formed by concatenating the first 6 primes: 2, 3, 5, 7, 11 and 13.
The corresponding Derived S-W number is '312010100' because '1' occurs 3 times, '3' occurs twice and '2', '5' and '7' all occur once.
- Task
- Find and show the first three S-W numbers which are prime.
- Find and show the first three Derived S-W numbers which are prime.
- Stretch (requires 'big integer' support)
Find and show the index in the sequence (starting from 1), the total number of digits and the last prime used to form the fourth, fifth, sixth, seventh and (optionally) the eighth S-W numbers which are prime or probably prime with reasonable certainty.
It is unknown whether there are any more but, if you fancy searching for one, good luck! You can start from an index of 22,077.
- References
- Wikipedia: Smarandache-Wellin number
- OEIS:A019518 - Smarandache-Wellin numbers
- OEIS:A069151 - Smarandache-Wellin primes
C
Basic
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <stdint.h>
bool isPrime(uint64_t n) {
if (n < 2) return false;
if (n%2 == 0) return n == 2;
if (n%3 == 0) return n == 3;
uint64_t d = 5;
while (d*d <= n) {
if (n%d == 0) return false;
d += 2;
if (n%d == 0) return false;
d += 4;
}
return true;
}
bool *sieve(int limit) {
int i, p;
limit++;
// True denotes composite, false denotes prime.
bool *c = calloc(limit, sizeof(bool)); // all false by default
c[0] = true;
c[1] = true;
for (i = 4; i < limit; i += 2) c[i] = true;
p = 3; // Start from 3.
while (true) {
int p2 = p * p;
if (p2 >= limit) break;
for (i = p2; i < limit; i += 2 * p) c[i] = true;
while (true) {
p += 2;
if (!c[p]) break;
}
}
return c;
}
int main() {
bool *c = sieve(400);
char sw[100] = "";
char tmp[20];
int swp[3];
int count = 0, p = 1, i;
while (count < 3) {
while (c[++p]);
sprintf(tmp, "%d", p);
strcat(sw, tmp);
int n = atoi(sw);
if (isPrime(n)) swp[count++] = n;
}
printf("The first 3 Smarandache-Wellin primes are:\n");
for (i = 0; i < 3; ++i) printf("%d ", swp[i]);
printf("\n");
int freqs[10] = {0};
uint64_t dswp[3];
count = 0;
p = 1;
while (count < 3) {
while (c[++p]);
sprintf(tmp, "%d", p);
for (i = 0; i < strlen(tmp); ++i) freqs[tmp[i]-48]++;
char dsw[20] = "";
for (i = 0; i < 10; ++i) {
sprintf(tmp, "%d", freqs[i]);
strcat(dsw, tmp);
}
int ix = -1;
for (i = 0; i < strlen(dsw); ++i) {
if (dsw[i] != '0') {
ix = i;
break;
}
}
uint64_t dn = atoll(dsw + ix);
if (isPrime(dn)) dswp[count++] = dn;
}
printf("\nThe first 3 Derived Smarandache-Wellin primes are:\n");
for (i = 0; i < 3; ++i) printf("%ld ", dswp[i]);
printf("\n");
free(c);
return 0;
}
- Output:
The first 3 Smarandache-Wellin primes are: 2 23 2357 The first 3 Derived Smarandache-Wellin primes are: 4194123321127 547233879626521 547233979727521
Stretch
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <stdint.h>
#include <gmp.h>
bool *sieve(int limit) {
int i, p;
limit++;
// True denotes composite, false denotes prime.
bool *c = calloc(limit, sizeof(bool)); // all false by default
c[0] = true;
c[1] = true;
for (i = 4; i < limit; i += 2) c[i] = true;
p = 3; // Start from 3.
while (true) {
int p2 = p * p;
if (p2 >= limit) break;
for (i = p2; i < limit; i += 2 * p) c[i] = true;
while (true) {
p += 2;
if (!c[p]) break;
}
}
return c;
}
int main() {
bool *c = sieve(12000);
char sw[6000] = "";
char tmp[20];
int count = 0, p = 1, ix = 0;
mpz_t n;
mpz_init(n);
printf("The 4th to the 8th Smarandache-Wellin primes are:\n");
while (count < 8) {
while (c[++p]);
sprintf(tmp, "%d", p);
strcat(sw, tmp);
mpz_set_str(n, sw, 10);
if (mpz_probab_prime_p(n, 15) > 0) {
count++;
if (count > 3) {
printf("%dth: index %4d digits %4ld last prime %5d\n", count, ix+1, strlen(sw), p);
}
}
ix++;
}
free(c);
return 0;
}
- Output:
The 4th to the 8th Smarandache-Wellin primes are: 4th: index 128 digits 355 last prime 719 5th: index 174 digits 499 last prime 1033 6th: index 342 digits 1171 last prime 2297 7th: index 435 digits 1543 last prime 3037 8th: index 1429 digits 5719 last prime 11927
Go
Basic
package main
import (
"fmt"
"rcu"
"strconv"
"strings"
)
func main() {
primes := rcu.Primes(400)
sw := ""
var swp []int
count := 0
i := 0
for count < 3 {
sw += strconv.Itoa(primes[i])
n, _ := strconv.Atoi(sw)
if rcu.IsPrime(n) {
swp = append(swp, n)
count++
}
i++
}
fmt.Println("The first 3 Smarandache-Wellin primes are:")
fmt.Printf("%v\n", swp)
freqs := make([]int, 10)
var dswp []int
count = 0
i = 0
for count < 3 {
p := strconv.Itoa(primes[i])
for _, d := range p {
n, _ := strconv.Atoi(string(d))
freqs[n]++
}
dsw := ""
for _, freq := range freqs {
dsw += strconv.Itoa(freq)
}
dsw = strings.TrimLeft(dsw, "0")
dn, _ := strconv.Atoi(dsw)
if rcu.IsPrime(dn) {
dswp = append(dswp, dn)
count++
}
i++
}
fmt.Println("\nThe first 3 Derived Smarandache-Wellin primes are:")
fmt.Printf("%v\n", dswp)
}
- Output:
The first 3 Smarandache-Wellin primes are: [2 23 2357] The first 3 Derived Smarandache-Wellin primes are: [4194123321127 547233879626521 547233979727521]
Stretch
We need to use the above GMP wrapper to match Wren's time of about 35.5 seconds as Go's native big.Int type is far slower.
package main
import (
"fmt"
big "github.com/ncw/gmp"
"rcu"
"strconv"
)
func main() {
primes := rcu.Primes(12000)
sw := ""
count := 0
i := 0
n := new(big.Int)
fmt.Println("The 4th to the 8th Smarandache-Wellin primes are:")
for count < 8 {
sw += strconv.Itoa(primes[i])
n.SetString(sw, 10)
if n.ProbablyPrime(15) {
count++
if count > 3 {
fmt.Printf("%dth: index %4d digits %4d last prime %5d\n", count, i+1,
len(sw), primes[i])
}
}
i++
}
}
- Output:
The 4th to the 8th Smarandache-Wellin primes are: 4th: index 128 digits 355 last prime 719 5th: index 174 digits 499 last prime 1033 6th: index 342 digits 1171 last prime 2297 7th: index 435 digits 1543 last prime 3037 8th: index 1429 digits 5719 last prime 11927
Raku
The first seven Smarandache-Wellin primes are found in a few seconds on my system. The eighth adds over five minutes to the run time.
use Lingua::EN::Numbers;
my @primes = (^∞).grep: &is-prime;
my @Smarandache-Whellen = [\~] @primes;
sink @Smarandache-Whellen[1500]; # pre-reify for concurrency
sub derived ($n) { my %digits = $n.comb.Bag; (0..9).map({ %digits{$_} // 0 }).join }
sub abbr ($_) { .chars < 41 ?? $_ !! .substr(0,20) ~ '…' ~ .substr(*-20) ~ " ({.chars} digits)" }
say "Smarandache-Whellen primes:";
say ordinal-digit(++$,:u).fmt("%4s") ~ $_ for (^∞).hyper(:4batch).map({
next unless (my $sw = @Smarandache-Whellen[$_]).is-prime;
sprintf ": Index: %4d, Last prime: %5d, %s", $_, @primes[$_], $sw.&abbr
})[^8];
say "\nSmarandache-Whellen derived primes:";
say ordinal-digit(++$,:u).fmt("%4s") ~ $_ for (^∞).hyper(:8batch).map({
next unless (my $sw = @Smarandache-Whellen[$_].&derived).is-prime;
sprintf ": Index: %4d, %s", $_, $sw
})[^20];
- Output:
Smarandache-Whellen primes: 1ˢᵗ: Index: 0, Last prime: 2, 2 2ⁿᵈ: Index: 1, Last prime: 3, 23 3ʳᵈ: Index: 3, Last prime: 7, 2357 4ᵗʰ: Index: 127, Last prime: 719, 23571113171923293137…73677683691701709719 (355 digits) 5ᵗʰ: Index: 173, Last prime: 1033, 23571113171923293137…10131019102110311033 (499 digits) 6ᵗʰ: Index: 341, Last prime: 2297, 23571113171923293137…22732281228722932297 (1171 digits) 7ᵗʰ: Index: 434, Last prime: 3037, 23571113171923293137…30013011301930233037 (1543 digits) 8ᵗʰ: Index: 1428, Last prime: 11927, 23571113171923293137…11903119091192311927 (5719 digits) Smarandache-Whellen derived primes: 1ˢᵗ: Index: 31, 4194123321127 2ⁿᵈ: Index: 71, 547233879626521 3ʳᵈ: Index: 72, 547233979727521 4ᵗʰ: Index: 133, 13672766322929571043 5ᵗʰ: Index: 224, 3916856106393739943689 6ᵗʰ: Index: 302, 462696313560586013558131 7ᵗʰ: Index: 308, 532727113760586013758133 8ᵗʰ: Index: 362, 6430314317473636515467149 9ᵗʰ: Index: 461, 8734722823685889120488197 10ᵗʰ: Index: 489, 9035923128899919621189209 11ᵗʰ: Index: 494, 9036023329699969621389211 12ᵗʰ: Index: 521, 9337023533410210710923191219 13ᵗʰ: Index: 537, 94374237357103109113243102223 14ᵗʰ: Index: 623, 117416265406198131121272110263 15ᵗʰ: Index: 720, 141459282456260193137317129313 16ᵗʰ: Index: 737, 144466284461264224139325131317 17ᵗʰ: Index: 789, 156483290479273277162351153339 18ᵗʰ: Index: 851, 164518312512286294233375158359 19ᵗʰ: Index: 1086, 208614364610327343341589284471 20ᵗʰ: Index: 1187, 229667386663354357356628334581
Wren
Basic
import "./math" for Int
import "./fmt" for Fmt
var primes = Int.primeSieve(400)
var sw = ""
var swp = []
var count = 0
var i = 0
while (count < 3) {
sw = sw + primes[i].toString
var n = Num.fromString(sw)
if (Int.isPrime(n)) {
swp.add(n)
count = count + 1
}
i = i + 1
}
System.print("The first 3 Smarandache-Wellin primes are:")
Fmt.print("$d", swp)
var freqs = List.filled(10, 0)
var dswp = []
count = 0
i = 0
while (count < 3) {
var p = primes[i].toString
for (d in p) {
var n = Num.fromString(d)
freqs[n] = freqs[n] + 1
}
var dsw = freqs.join("").trimStart("0")
var dn = Num.fromString(dsw)
if (Int.isPrime(dn)) {
dswp.add(dn)
count = count + 1
}
i = i + 1
}
System.print("\nThe first 3 Derived Smarandache-Wellin primes are:")
Fmt.print("$d", dswp)- Output:
The first 3 Smarandache-Wellin primes are: 2 23 2357 The first 3 Derived Smarandache-Wellin primes are: 4194123321127 547233879626521 547233979727521
Stretch
Need to use GMP here to find the 8th S-W prime in a reasonable time (35.5 seconds on my Core i7 machine).
import "./math" for Int
import "./gmp" for Mpz
import "./fmt"for Fmt
var primes = Int.primeSieve(12000)
var sw = ""
var count = 0
var i = 0
var n = Mpz.new()
System.print("The 4th to the 8th Smarandache-Wellin primes are:")
while (count < 8) {
sw = sw + primes[i].toString
n.setStr(sw)
if (n.probPrime(15) > 0) {
count = count + 1
if (count > 3) {
Fmt.print("$r: index $4d digits $4d last prime $5d", count, i+1, sw.count, primes[i])
}
}
i = i + 1
}- Output:
The 4th to the 8th Smarandache-Wellin primes are: 4th: index 128 digits 355 last prime 719 5th: index 174 digits 499 last prime 1033 6th: index 342 digits 1171 last prime 2297 7th: index 435 digits 1543 last prime 3037 8th: index 1429 digits 5719 last prime 11927