Composite numbers k with no single digit factors whose factors are all substrings of k
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.
Composite numbers k with no single digit factors whose factors are all substrings of k 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.
- Task
- Find and show here, on this page, the first ten elements of the sequence.
- Stretch
- Find and show the next ten elements.
ALGOL 68
<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 #
PROC is substring = ( STRING k str, INT f )BOOL:
BEGIN
STRING f str = whole( f, 0 );
INT f len = ( UPB f str - LWB f str ) + 1;
BOOL result := FALSE;
INT f end := ( LWB k str + f len ) - 2;
FOR f pos FROM LWB k str TO ( UPB k str + 1 ) - f len WHILE NOT result DO
f end +:= 1;
result := k str[ f pos : f end ] = f str
OD;
result
END # is substring # ;
# task #
INT required numbers = 20;
INT k count := 0;
# k must be odd and > 9 #
FOR k FROM 11 BY 2 WHILE k count < required numbers DO
IF k MOD 3 /= 0 AND k MOD 5 /= 0 AND k MOD 7 /= 0 THEN
# no single digit odd prime factors #
BOOL is candidate := TRUE;
STRING k str = whole( k, 0 );
INT v := k;
INT f count := 0;
FOR f FROM 11 BY 2 TO ENTIER sqrt( k ) + 1 WHILE v > 1 AND is candidate DO
IF v MOD f = 0 THEN
# have a factor #
is candidate := is substring( k str, f );
IF is candidate THEN
# the digits of f ae a substring of v #
WHILE v OVERAB f;
f count +:= 1;
v MOD f = 0
DO SKIP OD
FI
FI
OD;
IF is candidate AND ( f count > 1 OR ( v /= k AND v > 1 ) ) THEN
# have a composite whose factors are up to the root are substrings #
IF v > 1 THEN
# there was a factor > the root #
is candidate := is substring( k str, v )
FI;
IF is candidate THEN
print( ( " ", whole( k, -8 ) ) );
k count +:= 1;
IF k count MOD 10 = 0 THEN print( ( newline ) ) FI
FI
FI
FI
OD
END</lang>
- Output:
15317 59177 83731 119911 183347 192413 1819231 2111317 2237411 3129361 5526173 11610313 13436683 13731373 13737841 13831103 15813251 17692313 19173071 28118827
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(string, 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
Perl
<lang perl> use strict; use warnings; use ntheory qw<is_prime factor gcd>;
my($values,$cnt); LOOP: for (my $k = 11; $k < 1E10; $k += 2) {
next if 1 < gcd($k,2*3*5*7) or is_prime $k;
map { next if index($k, $_) < 0 } factor $k;
$values .= sprintf "%10d", $k;
last LOOP if ++$cnt == 20;
} print $values =~ s/.{1,100}\K/\n/gr;</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 "/seq" for Lst import "/fmt" for Fmt
var count = 0 var k = 11 * 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) {
Lst.prune(factors)
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