\\ PARI Program
\\ A076886: Smallest palindrome with exactly n prime factors (counted with multiplicity).
\\ The algorithm used here takes advantage of the observation that if the number of digits
\\ in the palindrome is small enough, then the prime factorization must include
\\ many 2's and 3's. Also, if the palindrome is divisible by 2 then it cannot also be divisible
\\ by 5 since a palindrome cannot be a multiple of 10. In this case, the remaining prime
\\ factors must be at least 7.
\\
\\ The algorithm is, however, essentially brute force - the speed up is at most a constant
\\ factor when compared with a linear search.
\\
\\ All terms up to a(50) have been computed with this program. The longest was a(48) taking
\\ more time than the rest combined (approx 8 hours).
a(n)={
my(dgs=logint(2^n,10)); while(1, dgs++; my(r=findA076886(dgs,n)); if(rbigomega(t)==n)) );
);
best
}
\\ Finds the smallest k such that b1^k * b2^(e-k) <= n.
\\ On entry n > 0, 0 < b1 < b2.
\\ If b1^k > n then no such k exists and oo is returned.
minpow(n, e, b1, b2)={
my(t=b1^e);
if (t > n, return(oo));
while (e > 0 && t/b1*b2 <= n, t=t/b1*b2; e--);
e;
}
maxldigits = 5; \\ Maximum number of lower digits. Hash table size will be up to 10^maxldigits.
maxmdigits = 3; \\ Maximum number of middle digits. Minor performance boost.
\\ Finds the first palindrome with a given number of digits that is a multiple of m
\\ and satisfies a test. If no palindrome can be found oo is returned.
\\
\\ Implementation note: The palindromes are constructed in three stages: upper,
\\ middle and lower. The upper stage corresponds with the outer most digits.
\\ The upper digits are constructed in the outer loop. The middle digits are
\\ obtained from a small precomputed table. This is a simple time saving measure.
\\ The lower digits are obtained from a pre-computed map (dictionary) indexed
\\ by the remainder needed to create the required divisibilty.
\\ There is a trade off in the time taken to build the lookup and the performance gain it gives.
\\ Performance tests indicate that for 21 digits and less the lookup works best with 10^4 entries.
\\ For 22 digits and up 10^5 entries is faster but requires more memory.
palwithdiv(dgs, m, test)={
\\ Initialise number of digits in each segment
my( gdgs = (dgs+1)\2,
ldgs = min(min(gdgs-1, logint(3*m,10)), min((dgs-1)\4, maxldigits)),
mdgs = min(gdgs-1-ldgs, maxmdigits),
udgs = gdgs - ldgs - mdgs );
\\ Initialise data structures for lower and middle segments
my( LMap = buildlookup(dgs, 10^ldgs, m),
MVect = vector(10^mdgs, mx, mkpal(dgs, (mx-1)*10^ldgs)) );
for(ux=10^(udgs-1), 10^udgs-1,
my(upal=mkpal(dgs, ux*10^(mdgs+ldgs)));
if(valuation(upal,2) >= min(udgs, valuation(m,2)),
for(mx=1, #MVect,
my(mpal=upal+MVect[mx], hk=mpal%m-m, z);
while(mapisdefined(LMap, hk, &z),
my(pal=z+mpal);
if(test(pal), return(pal));
hk=z;
)
)
)
);
oo
}
\\ Helper to build lookup table for lower digits of palindrome indexed by residue.
\\ Two palindromes may have the same residue. In this case they are encoded in a linked list
\\ from smallest to largest.
buildlookup(dgs, len, m)={
my(M=Map());
for( k=0, len-1,
my(pal = mkpal(dgs, k), hk = (-pal % m) - m, z);
while(mapisdefined(M, hk, &z), hk = z);
mapput(M, hk, pal) );
M
}
\\ Creates a palindrome with dgs digits with the most significant digits being n.
\\ Can be used to construct both even length and odd length palindromes.
\\ On entry: dgs>=1, 0 <= n < 10^ceiling(dgs/2).
mkpal(dgs, n)={if(!n, 0, my(e=1+logint(n,10)); n*10^(dgs\2) + fromdigits(Vecrev(digits(if(dgs%2,n\10,n))))*10^((dgs+1)\2-e)) }
\\ End