Rosetta Code

Smarandache-Wellin primes

Revision as of 08:57, 28 March 2023 by PureFox (talk | contribs) (→‎{{header|Wren}}: Merged the two previous solutions into one and also do extended stretch goal.)

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.

Also find and show the fourth up to the twentieth Derived S-W numbers which are prime and their index in the sequence.

References


C

Translation of: Wren

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

Library: GMP
#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

Translation of: Wren

Basic

Library: Go-rcu
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

Library: GMP(Go wrapper)

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

Phix

Rather slow... 

with javascript_semantics
include mpfr.e
string sw = ""
mpz n = mpz_init(), dn = mpz_init()
sequence swp = {}, swdp = {}, dc = repeat(0,10)
integer np = 0
atom t0 = time(), t1 = time()+1
while length(swp)<iff(platform()=JS?5:8) do
    np += 1
    integer p = get_prime(np)
    string sp = sprintf("%d",p)
    sw &= sp
    mpz_set_str(n,sw,10)
    if mpz_prime(n) then
        swp = append(swp,{np,p,shorten(sw)})
    end if
    for c in sp do
        dc[c-'0'+1] += 1
    end for
    integer dc9 = dc[10]
    if odd(dc9) and remainder(dc9,5)!=0 then
        string swdps = join(dc,"",fmt:="%d")
        mpz_set_str(dn,swdps,10)
        if mpz_prime(dn) then
            swdp = append(swdp,{np,swdps})
        end if
    end if
    if platform()!=JS and time()>t1 then
        progress("processing prime %d...\r",{np})
        t1 = time()+1
    end if
end while
printf(1,"Smarandache-Whellen primes:\n")
for i,s in swp do
    printf(1," %d%s:",{i,ord(i)})
    printf(1," Index: %4d, Last prime %5d, %s\n",s)
end for
printf(1,"Smarandache-Whellen derived primes:\n")
for i,s in swdp do
    printf(1," %d%s:",{i,ord(i)})
    printf(1," Index: %4d, %s\n",s)
end for
?elapsed(time()-t0)
Output:
Smarandache-Whellen primes:
 1st: Index:    1, Last prime     2, 2
 2nd: Index:    2, Last prime     3, 23
 3rd: Index:    4, Last prime     7, 2357
 4th: Index:  128, Last prime   719, 23571113171923293137...73677683691701709719 (355 digits)
 5th: Index:  174, Last prime  1033, 23571113171923293137...10131019102110311033 (499 digits)
 6th: Index:  342, Last prime  2297, 23571113171923293137...22732281228722932297 (1,171 digits)
 7th: Index:  435, Last prime  3037, 23571113171923293137...30013011301930233037 (1,543 digits)
 8th: Index: 1429, Last prime 11927, 23571113171923293137...11903119091192311927 (5,719 digits)
Smarandache-Whellen derived primes:
 1st: Index:   32, 4194123321127
 2nd: Index:   72, 547233879626521
 3rd: Index:   73, 547233979727521
 4th: Index:  134, 13672766322929571043
 5th: Index:  225, 3916856106393739943689
 6th: Index:  303, 462696313560586013558131
 7th: Index:  309, 532727113760586013758133
 8th: Index:  363, 6430314317473636515467149
 9th: Index:  462, 8734722823685889120488197
 10th: Index:  490, 9035923128899919621189209
 11th: Index:  495, 9036023329699969621389211
 12th: Index:  522, 9337023533410210710923191219
 13th: Index:  538, 94374237357103109113243102223
 14th: Index:  624, 117416265406198131121272110263
 15th: Index:  721, 141459282456260193137317129313
 16th: Index:  738, 144466284461264224139325131317
 17th: Index:  790, 156483290479273277162351153339
 18th: Index:  852, 164518312512286294233375158359
 19th: Index: 1087, 208614364610327343341589284471
 20th: Index: 1188, 229667386663354357356628334581
"13 minutes and 13s"

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

Library: Wren-math
Library: Wren-fmt
Library: Wren-gmp

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 known Smarandache-Wellin primes are:")
while (count < 8) {
    sw = sw + primes[i].toString
    n.setStr(sw)
    if (n.probPrime(15) > 0) {
        count = count + 1
        Fmt.print("$r: index $4d  digits $4d  last prime $5d -> $20a", count, i+1, sw.count, primes[i], n)
    }
    i = i + 1
}

System.print("\nThe first 20 Derived Smarandache-Wellin primes are:")
var freqs = List.filled(10, 0)
count = 0
i = 0
while (count < 20) {
    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")
    n.setStr(dsw)
    if (n.probPrime(15) > 0) {
        count = count + 1
        Fmt.print("$4r: index $4d  prime $i", count, i+1, n)
    }
    i = i + 1
}
Output:
The known Smarandache-Wellin primes are:
1st: index    1  digits    1  last prime     2 -> 2
2nd: index    2  digits    2  last prime     3 -> 23
3rd: index    4  digits    4  last prime     7 -> 2357
4th: index  128  digits  355  last prime   719 -> 23571113171923293137...73677683691701709719
5th: index  174  digits  499  last prime  1033 -> 23571113171923293137...10131019102110311033
6th: index  342  digits 1171  last prime  2297 -> 23571113171923293137...22732281228722932297
7th: index  435  digits 1543  last prime  3037 -> 23571113171923293137...30013011301930233037
8th: index 1429  digits 5719  last prime 11927 -> 23571113171923293137...11903119091192311927

The first 20 Derived Smarandache-Wellin primes are:
 1st: index   32  prime 4194123321127
 2nd: index   72  prime 547233879626521
 3rd: index   73  prime 547233979727521
 4th: index  134  prime 13672766322929571043
 5th: index  225  prime 3916856106393739943689
 6th: index  303  prime 462696313560586013558131
 7th: index  309  prime 532727113760586013758133
 8th: index  363  prime 6430314317473636515467149
 9th: index  462  prime 8734722823685889120488197
10th: index  490  prime 9035923128899919621189209
11th: index  495  prime 9036023329699969621389211
12th: index  522  prime 9337023533410210710923191219
13th: index  538  prime 94374237357103109113243102223
14th: index  624  prime 117416265406198131121272110263
15th: index  721  prime 141459282456260193137317129313
16th: index  738  prime 144466284461264224139325131317
17th: index  790  prime 156483290479273277162351153339
18th: index  852  prime 164518312512286294233375158359
19th: index 1087  prime 208614364610327343341589284471
20th: index 1188  prime 229667386663354357356628334581
Retrieved from "https://rosettacode.org/wiki/Smarandache-Wellin_primes?oldid=339482"