upto(n) = pairsWhereAtLeastOnePrimePowerHasAnExponentLargerThan2InTheFactorization(n) pairsWhereAtLeastOnePrimePowerHasAnExponentLargerThan2InTheFactorization(n) = {my(powersList = List()); res = List(); for(i = 3, logint(n, 2), forprime(j = 2, sqrtnint(n, i), listput(powersList, j^i); ) ); listsort(powersList, 1); for(i = 1, #powersList, process(powersList[i]); ); for(i = 2, #powersList, if(sqrtint(powersList[i-1]) == sqrtint(powersList[i]), if(nextprime(powersList[i-1]) > powersList[i], listput(res, powersList[i-1]); listput(res, powersList[i]); ) ) ); listsort(res); res } process(n) = { my(precsquare = sqrtint(n-1)^2, nextsquare = ceil(sqrt(n+1))^2); if(nextprime(precsquare) > n && isprimepower(precsquare), listput(res, precsquare); listput(res, n)); if(nextprime(n) > nextsquare && isprimepower(nextsquare), listput(res, n); listput(res, nextsquare)); }