Composite numbers k with no single digit factors whose factors are all substrings of k: Difference between revisions
Content added Content deleted
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
|||
Line 18: | Line 18: | ||
=={{header|ALGOL 68}}== |
=={{header|ALGOL 68}}== |
||
< |
<syntaxhighlight lang="algol68">BEGIN # find composite k with no single digit factors whose factors are all substrings of k # |
||
# returns TRUE if the string representation of f is a substring of k str, FALSE otherwise # |
# returns TRUE if the string representation of f is a substring of k str, FALSE otherwise # |
||
PROC is substring = ( STRING k str, INT f )BOOL: |
PROC is substring = ( STRING k str, INT f )BOOL: |
||
Line 70: | Line 70: | ||
FI |
FI |
||
OD |
OD |
||
END</ |
END</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 79: | Line 79: | ||
=={{header|Arturo}}== |
=={{header|Arturo}}== |
||
< |
<syntaxhighlight lang="rebol">valid?: function [n][ |
||
pf: factors.prime n |
pf: factors.prime n |
||
every? pf 'f -> |
every? pf 'f -> |
||
Line 95: | Line 95: | ||
] |
] |
||
'i + 2 |
'i + 2 |
||
]</ |
]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 112: | Line 112: | ||
=={{header|F_Sharp|F#}}== |
=={{header|F_Sharp|F#}}== |
||
Can anything be described as a translation of J? I use a wheel as described in J's comments, but of course I use numerical methods not euyuk! strings. |
Can anything be described as a translation of J? I use a wheel as described in J's comments, but of course I use numerical methods not euyuk! strings. |
||
< |
<syntaxhighlight lang="fsharp"> |
||
// Composite numbers k with no single digit factors whose factors are all substrings of k. Nigel Galloway: January 28th., 2022 |
// Composite numbers k with no single digit factors whose factors are all substrings of k. Nigel Galloway: January 28th., 2022 |
||
let fG n g=let rec fN i g e l=match i<g,g=0L,i%10L=g%10L with (true,_,_)->false |(_,true,_)->true |(_,_,true)->fN(i/10L)(g/10L) e l |_->fN l e e (l/10L) in fN n g g (n/10L) |
let fG n g=let rec fN i g e l=match i<g,g=0L,i%10L=g%10L with (true,_,_)->false |(_,true,_)->true |(_,_,true)->fN(i/10L)(g/10L) e l |_->fN l e e (l/10L) in fN n g g (n/10L) |
||
Line 118: | Line 118: | ||
Seq.unfold(fun n->Some(n|>List.filter(fun(n:int64)->not(Open.Numeric.Primes.Prime.Numbers.IsPrime &n) && fN n),n|>List.map((+)210L)))([1L..2L..209L] |
Seq.unfold(fun n->Some(n|>List.filter(fun(n:int64)->not(Open.Numeric.Primes.Prime.Numbers.IsPrime &n) && fN n),n|>List.map((+)210L)))([1L..2L..209L] |
||
|>List.filter(fun n->n%3L>0L && n%5L>0L && n%7L>0L))|>Seq.concat|>Seq.skip 1|>Seq.take 20|>Seq.iter(printfn "%d") |
|>List.filter(fun n->n%3L>0L && n%5L>0L && n%7L>0L))|>Seq.concat|>Seq.skip 1|>Seq.take 20|>Seq.iter(printfn "%d") |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 147: | Line 147: | ||
{{trans|Wren}} |
{{trans|Wren}} |
||
{{libheader|Go-rcu}} |
{{libheader|Go-rcu}} |
||
< |
<syntaxhighlight lang="go">package main |
||
import ( |
import ( |
||
Line 195: | Line 195: | ||
} |
} |
||
fmt.Println() |
fmt.Println() |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 204: | Line 204: | ||
=={{header|J}}== |
=={{header|J}}== |
||
< |
<syntaxhighlight lang="j"> */2 3 5 7 |
||
210 |
210 |
||
#1+I.0=+/|:4 q:1+i.210 |
#1+I.0=+/|:4 q:1+i.210 |
||
48</ |
48</syntaxhighlight> |
||
Or: 48 out of every 210 positive numbers have no single digit factors. |
Or: 48 out of every 210 positive numbers have no single digit factors. |
||
Line 213: | Line 213: | ||
So, we can generate a few hundred thousand lists of 48 numbers, discard the primes (and 1), then check what's left using substring matching on the factors. (We allow '0' as a 'factor' in our substring test so that we can work with a padded array of factors, avoiding variable length factor lists.) |
So, we can generate a few hundred thousand lists of 48 numbers, discard the primes (and 1), then check what's left using substring matching on the factors. (We allow '0' as a 'factor' in our substring test so that we can work with a padded array of factors, avoiding variable length factor lists.) |
||
< |
<syntaxhighlight lang="j"> 2{._10 ]\(#~ */"1@((+./@(E. '0 ',])~&>)&:(":&.>)q:))(#~ 1-1&p:)}.,(1+I.0=+/|:4 q:1+i.210)+/~210*i.2e5 |
||
15317 59177 83731 119911 183347 192413 1819231 2111317 2237411 3129361 |
15317 59177 83731 119911 183347 192413 1819231 2111317 2237411 3129361 |
||
5526173 11610313 13436683 13731373 13737841 13831103 15813251 17692313 19173071 28118827</ |
5526173 11610313 13436683 13731373 13737841 13831103 15813251 17692313 19173071 28118827</syntaxhighlight> |
||
Most of the time here is the substring testing, so this could be better optimized. |
Most of the time here is the substring testing, so this could be better optimized. |
||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
< |
<syntaxhighlight lang="julia">using Lazy |
||
using Primes |
using Primes |
||
Line 231: | Line 231: | ||
foreach(p -> print(lpad(last(p), 9), first(p) == 10 ? "\n" : ""), enumerate(take(20, seq))) |
foreach(p -> print(lpad(last(p), 9), first(p) == 10 ? "\n" : ""), enumerate(take(20, seq))) |
||
</ |
</syntaxhighlight>{{out}} |
||
<pre> |
<pre> |
||
15317 59177 83731 119911 183347 192413 1819231 2111317 2237411 3129361 |
15317 59177 83731 119911 183347 192413 1819231 2111317 2237411 3129361 |
||
Line 238: | Line 238: | ||
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
||
< |
<syntaxhighlight lang="mathematica">ClearAll[CompositeAndContainsPrimeFactor] |
||
CompositeAndContainsPrimeFactor[k_Integer] := Module[{id, pf}, |
CompositeAndContainsPrimeFactor[k_Integer] := Module[{id, pf}, |
||
If[CompositeQ[k], |
If[CompositeQ[k], |
||
Line 252: | Line 252: | ||
] |
] |
||
] |
] |
||
out = Select[Range[30000000], CompositeAndContainsPrimeFactor]</ |
out = Select[Range[30000000], CompositeAndContainsPrimeFactor]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>{15317, 59177, 83731, 119911, 183347, 192413, 1819231, 2111317, 2237411, 3129361, 5526173, 11610313, 13436683, 13731373, 13737841, 13831103, 15813251, 17692313, 19173071, 28118827}</pre> |
<pre>{15317, 59177, 83731, 119911, 183347, 192413, 1819231, 2111317, 2237411, 3129361, 5526173, 11610313, 13436683, 13731373, 13737841, 13831103, 15813251, 17692313, 19173071, 28118827}</pre> |
||
Line 259: | Line 259: | ||
==={{header|Free Pascal}}=== |
==={{header|Free Pascal}}=== |
||
modified [[Factors_of_an_integer#using_Prime_decomposition]] |
modified [[Factors_of_an_integer#using_Prime_decomposition]] |
||
< |
<syntaxhighlight lang="pascal">program FacOfInt; |
||
// gets factors of consecutive integers fast |
// gets factors of consecutive integers fast |
||
// limited to 1.2e11 |
// limited to 1.2e11 |
||
Line 617: | Line 617: | ||
writeln('runtime ',T0/1000:0:3,' s'); |
writeln('runtime ',T0/1000:0:3,' s'); |
||
end. |
end. |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out|@TIO.RUN}} |
{{out|@TIO.RUN}} |
||
<pre style="height:480px"> |
<pre style="height:480px"> |
||
Line 818: | Line 818: | ||
{{trans|Raku}} |
{{trans|Raku}} |
||
{{libheader|ntheory}} |
{{libheader|ntheory}} |
||
< |
<syntaxhighlight lang="perl"> use strict; |
||
use warnings; |
use warnings; |
||
use ntheory qw<is_prime factor gcd>; |
use ntheory qw<is_prime factor gcd>; |
||
Line 829: | Line 829: | ||
last LOOP if ++$cnt == 20; |
last LOOP if ++$cnt == 20; |
||
} |
} |
||
print $values =~ s/.{1,100}\K/\n/gr;</ |
print $values =~ s/.{1,100}\K/\n/gr;</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> 15317 59177 83731 119911 183347 192413 1819231 2111317 2237411 3129361 |
<pre> 15317 59177 83731 119911 183347 192413 1819231 2111317 2237411 3129361 |
||
Line 836: | Line 836: | ||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
{{trans|Wren}} |
{{trans|Wren}} |
||
<!--< |
<!--<syntaxhighlight lang="phix">(phixonline)--> |
||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
||
<span style="color: #004080;">integer</span> <span style="color: #000000;">count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">11</span><span style="color: #0000FF;">*</span><span style="color: #000000;">11</span><span style="color: #0000FF;">,</span> |
<span style="color: #004080;">integer</span> <span style="color: #000000;">count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">11</span><span style="color: #0000FF;">*</span><span style="color: #000000;">11</span><span style="color: #0000FF;">,</span> |
||
Line 866: | Line 866: | ||
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span> |
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span> |
||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Total time:%s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)})</span> |
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Total time:%s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)})</span> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
{{out}} |
{{out}} |
||
<small>(As usual, limiting to the first 10 under pwa/p2js keeps the time staring at a blank screen under 10s)</small> |
<small>(As usual, limiting to the first 10 under pwa/p2js keeps the time staring at a blank screen under 10s)</small> |
||
Line 896: | Line 896: | ||
The obvious problem with the above is that prime_factors() quite literally does not know when to quit. |
The obvious problem with the above is that prime_factors() quite literally does not know when to quit. |
||
Output as above, except Total time is reduced to 47s. |
Output as above, except Total time is reduced to 47s. |
||
<!--< |
<!--<syntaxhighlight lang="phix">(phixonline)--> |
||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
||
<span style="color: #004080;">integer</span> <span style="color: #000000;">count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">11</span><span style="color: #0000FF;">*</span><span style="color: #000000;">11</span><span style="color: #0000FF;">,</span> |
<span style="color: #004080;">integer</span> <span style="color: #000000;">count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">11</span><span style="color: #0000FF;">*</span><span style="color: #000000;">11</span><span style="color: #0000FF;">,</span> |
||
Line 933: | Line 933: | ||
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span> |
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span> |
||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Total time:%s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)})</span> |
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Total time:%s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)})</span> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
=={{header|Python}}== |
=={{header|Python}}== |
||
< |
<syntaxhighlight lang="python">from sympy import isprime, factorint |
||
def contains_its_prime_factors_all_over_7(n): |
def contains_its_prime_factors_all_over_7(n): |
||
Line 952: | Line 952: | ||
if found == 20: |
if found == 20: |
||
break |
break |
||
</ |
</syntaxhighlight>{{out}} |
||
<pre> |
<pre> |
||
15,317 59,177 83,731 119,911 183,347 192,413 1,819,231 2,111,317 2,237,411 3,129,361 |
15,317 59,177 83,731 119,911 183,347 192,413 1,819,231 2,111,317 2,237,411 3,129,361 |
||
Line 960: | Line 960: | ||
=={{header|Raku}}== |
=={{header|Raku}}== |
||
<lang |
<syntaxhighlight lang="raku" line>use Prime::Factor; |
||
use Lingua::EN::Numbers; |
use Lingua::EN::Numbers; |
||
Line 966: | Line 966: | ||
next if (1 < $_ gcd 210) || .is-prime || any .&prime-factors.map: -> $n { !.contains: $n }; |
next if (1 < $_ gcd 210) || .is-prime || any .&prime-factors.map: -> $n { !.contains: $n }; |
||
$_ |
$_ |
||
} )[^20].batch(10)».&comma».fmt("%10s").join: "\n";</ |
} )[^20].batch(10)».&comma».fmt("%10s").join: "\n";</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 973: | Line 973: | ||
=={{header|Sidef}}== |
=={{header|Sidef}}== |
||
< |
<syntaxhighlight lang="ruby">var e = Enumerator({|f| |
||
var c = (9.primorial) |
var c = (9.primorial) |
||
Line 993: | Line 993: | ||
say n |
say n |
||
break if (--count <= 0) |
break if (--count <= 0) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,012: | Line 1,012: | ||
{{libheader|Wren-seq}} |
{{libheader|Wren-seq}} |
||
{{libheader|Wren-fmt}} |
{{libheader|Wren-fmt}} |
||
< |
<syntaxhighlight lang="ecmascript">import "/math" for Int |
||
import "/seq" for Lst |
import "/seq" for Lst |
||
import "/fmt" for Fmt |
import "/fmt" for Fmt |
||
Line 1,043: | Line 1,043: | ||
} |
} |
||
Fmt.print("$,10d", res[0..9]) |
Fmt.print("$,10d", res[0..9]) |
||
Fmt.print("$,10d", res[10..19])</ |
Fmt.print("$,10d", res[10..19])</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,053: | Line 1,053: | ||
=={{header|XPL0}}== |
=={{header|XPL0}}== |
||
Runs in 33.6 seconds on Raspberry Pi 4. |
Runs in 33.6 seconds on Raspberry Pi 4. |
||
< |
<syntaxhighlight lang="xpl0">include xpllib; \for ItoA, StrFind and RlOutC |
||
int K, C; |
int K, C; |
||
Line 1,091: | Line 1,091: | ||
K:= K+2; \must be odd because all factors > 2 are odd primes |
K:= K+2; \must be odd because all factors > 2 are odd primes |
||
until C >= 20; |
until C >= 20; |
||
]</ |
]</syntaxhighlight> |
||
{{out}} |
{{out}} |