/*********************************************************
Languasco & Zaccagnini, Introduzione alla Crittografia, Hoepli. 
Capitolo 9.5 pag. 265
*********************************************************/

{root(n, k) = local(s);
   s = round(0.5 + n^(1/k));
   if(s^k > n, s--);
   return(s)}

{sum_p_and_pow(n,k) = local(s);
   s = root(n,k);
   for(i = 0, s, if(isprime(n - i^k), return(1)));
   if(n == s^k, return(1));
   return(-1)}

{HL(x,k) = local(t);
   t = 0;
   for(n = 1, x, if(sum_p_and_pow(n,k) > 0, t++));
   return(t)}

{except(x,k) = 
   for(n = 1, x, if(sum_p_and_pow(n,k) < 0, print(n)))}
      
      
{HL_rep(n,k) = local(s, t);
   s = root(n,k);
   t = 0;
   for(i = 0, s, if(isprime(n - i^k), t++));
   return(t)}