Composite numbers k with no single digit factors whose factors are all substrings of k: Difference between revisions
Composite numbers k with no single digit factors whose factors are all substrings of k (view source)
Revision as of 11:13, 8 February 2024
, 3 months agoAdd PARI/GP implementation
(Add PARI/GP implementation) |
|||
Line 690:
19: 19_173_071
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>
| |||