Composite numbers k with no single digit factors whose factors are all substrings of k: Difference between revisions

 

=={{header|ALGOL 68}}==

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

FI

OD

{{out}}

<pre>

=={{header|Arturo}}==

 

pf: factors.prime n

every? pf 'f ->

]

'i + 2

 

{{out}}

=={{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.

// 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)

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")

{{out}}

<pre>

{{trans|Wren}}

{{libheader|Go-rcu}}

 

import (

}

fmt.Println()

 

{{out}}

 

=={{header|J}}==

210

#1+I.0=+/|:4 q:1+i.210

 

Or: 48 out of every 210 positive numbers have no single digit factors.

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.)

 

15317 59177 83731 119911 183347 192413 1819231 2111317 2237411 3129361

 

Most of the time here is the substring testing, so this could be better optimized.

 

=={{header|Julia}}==

using Primes

 

 

foreach(p -> print(lpad(last(p), 9), first(p) == 10 ? "\n" : ""), enumerate(take(20, seq)))

<pre>

15317 59177 83731 119911 183347 192413 1819231 2111317 2237411 3129361

 

=={{header|Mathematica}}/{{header|Wolfram Language}}==

CompositeAndContainsPrimeFactor[k_Integer] := Module[{id, pf},

If[CompositeQ[k],

]

]

{{out}}

<pre>{15317, 59177, 83731, 119911, 183347, 192413, 1819231, 2111317, 2237411, 3129361, 5526173, 11610313, 13436683, 13731373, 13737841, 13831103, 15813251, 17692313, 19173071, 28118827}</pre>

==={{header|Free Pascal}}===

modified [[Factors_of_an_integer#using_Prime_decomposition]]

// gets factors of consecutive integers fast

// limited to 1.2e11

writeln('runtime ',T0/1000:0:3,' s');

end.

{{out|@TIO.RUN}}

<pre style="height:480px">

{{trans|Raku}}

{{libheader|ntheory}}

use warnings;

use ntheory qw<is_prime factor gcd>;

last LOOP if ++$cnt == 20;

}

{{out}}

<pre> 15317 59177 83731 119911 183347 192413 1819231 2111317 2237411 3129361

=={{header|Phix}}==

{{trans|Wren}}

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

{{out}}

<small>(As usual, limiting to the first 10 under pwa/p2js keeps the time staring at a blank screen under 10s)</small>

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.

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

 

=={{header|Python}}==

 

def contains_its_prime_factors_all_over_7(n):

if found == 20:

break

<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

=={{header|Raku}}==

 

use Lingua::EN::Numbers;

 

next if (1 < $_ gcd 210) || .is-prime || any .&prime-factors.map: -> $n { !.contains: $n };

$_

 

{{out}}

 

=={{header|Sidef}}==

 

var c = (9.primorial)

say n

break if (--count <= 0)

{{out}}

<pre>

{{libheader|Wren-seq}}

{{libheader|Wren-fmt}}

import "/seq" for Lst

import "/fmt" for Fmt

}

Fmt.print("$,10d", res[0..9])

 

{{out}}

=={{header|XPL0}}==

Runs in 33.6 seconds on Raspberry Pi 4.

int K, C;

 

K:= K+2; \must be odd because all factors > 2 are odd primes

until C >= 20;

 

{{out}}