Composite numbers k with no single digit factors whose factors are all substrings of k: Difference between revisions
Content added Content deleted
(Add PARI/GP implementation) |
|||
Line 690: | Line 690: | ||
19: 19_173_071 |
19: 19_173_071 |
||
20: 28_118_827 |
20: 28_118_827 |
||
</pre> |
|||
=={{header|PARI/GP}}== |
|||
<syntaxhighlight lang="PARI/GP"> |
|||
ssubstr(str,s=1,n=0)={ |
|||
my(vt=Vecsmall(str),ve,vr,vtn=#str,n1); |
|||
if(vtn==0,return("")); |
|||
if(s<1||s>vtn,return(str)); |
|||
n1=vtn-s+1; if(n==0,n=n1); if(n>n1,n=n1); |
|||
ve=vector(n,z,z-1+s); vr=vecextract(vt,ve); return(Strchr(vr)); |
|||
} |
|||
isSubstring(mainStr, subStr) = { |
|||
mainLen = #Vecsmall(mainStr); |
|||
subLen = #Vecsmall(subStr); |
|||
for (startPos=1, mainLen-subLen+1, |
|||
if (ssubstr(mainStr, startPos, subLen) == subStr, |
|||
return (1); /* True, found the substring */ |
|||
) |
|||
); |
|||
return (0); /* False, substring not found */ |
|||
} |
|||
\\ Determines if a number's factors, all > 9, are substrings of its decimal representation |
|||
contains_its_prime_factors_all_over_9(n) = { |
|||
if(n < 10 || isprime(n), return(0)); \\ Early return if n < 10 or n is prime |
|||
strn = Str(n); \\ Convert n to its string representation |
|||
pfacs = factor(n)[,1]; \\ Get the unique prime factors of n |
|||
\\print("n=" n ",pfacs=" pfacs); |
|||
for(i=1, #pfacs, |
|||
if(pfacs[i] <= 9, return(0)); \\ Skip factors not greater than 9 |
|||
if(!isSubstring(strn, Str(pfacs[i])), return(0)); \\ Check if factor is not a substring |
|||
); |
|||
return(1); \\ All conditions met |
|||
} |
|||
\\ Main loop to find numbers meeting the criteria |
|||
{ |
|||
found = 0; \\ Initialize counter |
|||
for(n=0, 30*10^6, \\ Iterate from 0 to 30 million |
|||
if(contains_its_prime_factors_all_over_9(n), |
|||
found += 1; \\ Increment counter if n meets the criteria |
|||
print1(n, " "); \\ Print n followed by a space |
|||
if(found % 10 == 0, print("")); \\ Print a newline every 10 numbers |
|||
if(found == 20, break); \\ Stop after finding 20 numbers |
|||
); |
|||
); |
|||
} |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
15317 59177 83731 119911 183347 192413 1819231 2111317 2237411 3129361 |
|||
5526173 11610313 13436683 13731373 13737841 13831103 15813251 17692313 19173071 28118827 |
|||
</pre> |
</pre> |
||