Smarandache-Wellin primes: Difference between revisions
(Changed the stretch goal to better reflect what people are actually doing.) |
(→{{header|Wren}}: Merged the two previous solutions into one and also do extended stretch goal.) |
||
Line 446: | Line 446: | ||
=={{header|Wren}}== |
=={{header|Wren}}== |
||
===Basic=== |
|||
{{libheader|Wren-math}} |
{{libheader|Wren-math}} |
||
{{libheader|Wren-fmt}} |
{{libheader|Wren-fmt}} |
||
⚫ | |||
⚫ | |||
<syntaxhighlight lang="ecmascript">import "./math" for Int |
<syntaxhighlight lang="ecmascript">import "./math" for Int |
||
import "./ |
import "./gmp" for Mpz |
||
⚫ | |||
var primes = Int.primeSieve( |
var primes = Int.primeSieve(12000) |
||
var sw = "" |
var sw = "" |
||
var swp = [] |
|||
var count = 0 |
var count = 0 |
||
var i = 0 |
var i = 0 |
||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
sw = sw + primes[i].toString |
sw = sw + primes[i].toString |
||
n.setStr(sw) |
|||
if ( |
if (n.probPrime(15) > 0) { |
||
swp.add(n) |
|||
count = count + 1 |
count = count + 1 |
||
⚫ | |||
} |
} |
||
i = i + 1 |
i = i + 1 |
||
} |
} |
||
⚫ | |||
Fmt.print("$d", swp) |
|||
⚫ | |||
var freqs = List.filled(10, 0) |
var freqs = List.filled(10, 0) |
||
var dswp = [] |
|||
count = 0 |
count = 0 |
||
i = 0 |
i = 0 |
||
while (count < |
while (count < 20) { |
||
var p = primes[i].toString |
var p = primes[i].toString |
||
for (d in p) { |
for (d in p) { |
||
Line 480: | Line 481: | ||
} |
} |
||
var dsw = freqs.join("").trimStart("0") |
var dsw = freqs.join("").trimStart("0") |
||
n.setStr(dsw) |
|||
if (Int.isPrime(dn)) { |
|||
dswp.add(dn) |
|||
count = count + 1 |
|||
} |
|||
i = i + 1 |
|||
} |
|||
⚫ | |||
Fmt.print("$d", dswp)</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
⚫ | |||
2 23 2357 |
|||
The first 3 Derived Smarandache-Wellin primes are: |
|||
4194123321127 547233879626521 547233979727521 |
|||
</pre> |
|||
===Stretch=== |
|||
⚫ | |||
⚫ | |||
<syntaxhighlight lang="ecmascript">import "./math" for Int |
|||
import "./gmp" for Mpz |
|||
⚫ | |||
var primes = Int.primeSieve(12000) |
|||
var sw = "" |
|||
var count = 0 |
|||
var i = 0 |
|||
⚫ | |||
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) { |
if (n.probPrime(15) > 0) { |
||
count = count + 1 |
count = count + 1 |
||
Fmt.print("$4r: index $4d prime $i", count, i+1, n) |
|||
⚫ | |||
} |
|||
} |
} |
||
i = i + 1 |
i = i + 1 |
||
Line 526: | Line 491: | ||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
The |
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 |
|||
⚫ | |||
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 |
|||
</pre> |
</pre> |
Revision as of 08:57, 28 March 2023
- Definitions
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.
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
- 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
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
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