Composite numbers k with no single digit factors whose factors are all substrings of k: Difference between revisions
m (→{{header|Phix}}: use gcd() (no faster just neater)) |
|||
Line 43: | Line 43: | ||
<span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">(),</span> <span style="color: #000000;">t1</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span> |
<span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">(),</span> <span style="color: #000000;">t1</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span> |
||
<span style="color: #008080;">while</span> <span style="color: #000000;">count</span><span style="color: #0000FF;"><</span><span style="color: #000000;">limit</span> <span style="color: #008080;">do</span> |
<span style="color: #008080;">while</span> <span style="color: #000000;">count</span><span style="color: #0000FF;"><</span><span style="color: #000000;">limit</span> <span style="color: #008080;">do</span> |
||
<span style="color: #008080;">if</span> <span style="color: #7060A8;"> |
<span style="color: #008080;">if</span> <span style="color: #7060A8;">gcd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">*</span><span style="color: #000000;">5</span><span style="color: #0000FF;">*</span><span style="color: #000000;">7</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span> |
||
<span style="color: #008080;">and</span> <span style="color: #7060A8;">remainder</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">)!=</span><span style="color: #000000;">0</span> |
|||
<span style="color: #008080;">and</span> <span style="color: #7060A8;">remainder</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7</span><span style="color: #0000FF;">)!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">f</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">prime_factors</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #004600;">true</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> |
<span style="color: #004080;">sequence</span> <span style="color: #000000;">f</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">prime_factors</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #004600;">true</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> |
||
<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">f</span><span style="color: #0000FF;">)></span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span> |
<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">f</span><span style="color: #0000FF;">)></span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span> |
Revision as of 02:10, 20 January 2022
Find the composite numbers k in base 10, that have no single digit prime factors and whose prime factors are all a substring of k.
- Task
- Find and show here, on this page, the first ten elements of the sequence.
- Stretch
- Find and show the next ten elements.
Julia
<lang julia>using Lazy using Primes
function containsitsonlytwodigfactors(n)
s = string(n) return !isprime(n) && all(t -> length(t) > 1 && contains(s, t), map(x -> string(x), collect(keys(factor(n)))))
end
seq = @>> Lazy.range(2) filter(containsitsonlytwodigfactors)
foreach(p -> print(lpad(last(p), 9), first(p) == 10 ? "\n" : ""), enumerate(take(20, seq)))
</lang>
- Output:
15317 59177 83731 119911 183347 192413 1819231 2111317 2237411 3129361 5526173 11610313 13436683 13731373 13737841 13831103 15813251 17692313 19173071 28118827
Phix
with javascript_semantics integer count = 0, n = 11*11, limit = iff(platform()=JS?10:20) atom t0 = time(), t1 = time() while count<limit do if gcd(n,3*5*7)=1 then sequence f = prime_factors(n,true,-1) if length(f)>1 then string s = sprintf("%d",n) bool valid = true for i=1 to length(f) do if (i=1 or f[i]!=f[i-1]) and not match(sprintf("%d",f[i]),s) then valid = false exit end if end for if valid then count += 1 string t = join(apply(f,sprint),"x"), e = elapsed(time()-t1) printf(1,"%2d: %,10d = %-17s (%s)\n",{count,n,t,e}) t1 = time() end if end if end if n += 2 end while printf(1,"Total time:%s\n",{elapsed(time()-t0)})
- Output:
(As usual, limiting to the first 10 under pwa/p2js keeps the time staring at a blank screen under 10s)
1: 15,317 = 17x17x53 (0s) 2: 59,177 = 17x59x59 (0.1s) 3: 83,731 = 31x37x73 (0.0s) 4: 119,911 = 11x11x991 (0.0s) 5: 183,347 = 47x47x83 (0.1s) 6: 192,413 = 13x19x19x41 (0.0s) 7: 1,819,231 = 19x23x23x181 (3.5s) 8: 2,111,317 = 13x13x13x31x31 (0.7s) 9: 2,237,411 = 11x11x11x41x41 (0.4s) 10: 3,129,361 = 29x29x61x61 (2.6s) 11: 5,526,173 = 17x61x73x73 (7.5s) 12: 11,610,313 = 11x11x11x11x13x61 (23.2s) 13: 13,436,683 = 13x13x43x43x43 (7.9s) 14: 13,731,373 = 73x137x1373 (1.3s) 15: 13,737,841 = 13x13x13x13x13x37 (0.0s) 16: 13,831,103 = 11x13x311x311 (0.4s) 17: 15,813,251 = 251x251x251 (8.9s) 18: 17,692,313 = 23x769231 (9.0s) 19: 19,173,071 = 19x19x173x307 (7.1s) 20: 28,118,827 = 11x11x281x827 (46.2s) Total time:1 minute and 59s
Raku
<lang perl6>use Prime::Factor; use Lingua::EN::Numbers;
put (2..∞).hyper(:5000batch).map( {
next if (1 < $_ gcd 210) || .is-prime || any .&prime-factors.map: -> $n { !.contains: $n }; $_
} )[^20].batch(10)».&comma».fmt("%10s").join: "\n";</lang>
- Output:
15,317 59,177 83,731 119,911 183,347 192,413 1,819,231 2,111,317 2,237,411 3,129,361 5,526,173 11,610,313 13,436,683 13,731,373 13,737,841 13,831,103 15,813,251 17,692,313 19,173,071 28,118,827
Wren
<lang ecmascript>import "/math" for Int import "/fmt" for Fmt
var count = 0 var k = 11 var res = [] while (count < 20) {
if (k % 3 == 0 || k % 5 == 0 || k % 7 == 0) { k = k + 2 continue } var factors = Int.primeFactors(k) if (factors.count > 1) { var s = k.toString var includesAll = true for (f in factors) { if (s.indexOf(f.toString) == -1) { includesAll = false break } } if (includesAll) { res.add(k) count = count + 1 } } k = k + 2
} Fmt.print("$,10d", res[0..9]) Fmt.print("$,10d", res[10..19])</lang>
- Output:
15,317 59,177 83,731 119,911 183,347 192,413 1,819,231 2,111,317 2,237,411 3,129,361 5,526,173 11,610,313 13,436,683 13,731,373 13,737,841 13,831,103 15,813,251 17,692,313 19,173,071 28,118,827