Determine the number of ordered pairs of prime numbers (p, q) such that N = p^2+q^3 is such that each digit from 0 to 9 appears exactly once

Question

I have to write a program such that can determine the number of ordered pairs of prime numbers (p, q) such that when N = p^2+q^3 is written in decimal, each digit from 0 to 9 appears exactly once (without leading zeroes).

I thought of using a variation of a sieve of Eratosthenes as it's explained here, however it's also mentioned that a sieve only works for numbers N such that N is less than ten million but by the statement of the problem each N is at least one hundred millions from the fact that each digit appears exactly once and there's no leading zeroes, but I don't have any other ideas apart from this one so any help would be appreciated.

Answer 1

Following the same technique as @Dave, but with a variable initial value for the inner loop, we get about 20% less iterations. I think this would be the optimal way. Here is an example using php, with access to 2 functions: p() is the nth prime and pi() is the prime counting function.

$nbr = 0;
$min = 1023456789;
$max = 9876543210;

for($i = 1; $i <= pi(floor(sqrt($max-2**3))); $i++){
    $p = p($i);
    for($j = pi(floor(max([0,$min-p($i)**2])**(1/3)))+1; $j <= pi(floor(($max-p($i)**2)**(1/3))); $j++){ 
        $q = p($j);
        $n = $p**2+$q**3;

        $arr = str_split($n);
        sort($arr);
        if(join("", $arr) === '0123456789'){
            $nbr++;
        }
    }
}

echo $nbr;

Output:

1270

Note: the max() function is to avoid errors with cubic root of negative numbers.

Answer 2

Take advantage of the fact that the largest prime you can cube and still form a potentially valid number is 2143.

Ruby code (read as pseudocode if you don't use Ruby):

require 'prime'
    
def f()
  # Determine the max & min numbers that can be made with 10 distinct digits and no leading zeroes
  max_num = 9_876_543_210
  min_num = 1_023_456_789
  
  # Find the largest prime having a cube <= max_num
  max_prime_to_cube = 2143
  
  count = 0
  
  # Cube every prime up to 2143 
  Prime.each do |prime_to_cube|
    return count if prime_to_cube > max_prime_to_cube
    cubed_val = prime_to_cube ** 3
    
    # Try adding the square of every prime until we exceed the maximum valid number
    Prime.each do |prime_to_square|
      squared_val = prime_to_square ** 2
      combined_val = squared_val + cubed_val
      next if combined_val < min_num
      break if combined_val > max_num
      
      # Check if all digits are unique
      if has_each_digit_once(combined_val)
        count += 1
        puts "val: #{combined_val} = #{prime_to_square}^2 + #{prime_to_cube}^3, count: #{count}"
      end
    end
  end
end


# Check each digit, setting bits of check_int where the i'th bit represents digit i
def has_each_digit_once(val_to_check)
  check_int = 0
  10.times do
    check_bit = 1 << (val_to_check % 10)
    
    # Exit early if we see a digit for the second time
    return false if check_bit & check_int > 0
    
    check_int |= check_bit
    val_to_check /= 10
  end
  return check_int == 1023
end

Results:

> f
val: 1328675409 = 36451^2 + 2^3, count: 1
val: 1478325609 = 38449^2 + 2^3, count: 2
val: 3085469217 = 55547^2 + 2^3, count: 3
val: 3507126849 = 59221^2 + 2^3, count: 4
...
val: 9682357410 = 5689^2 + 2129^3, count: 1267
val: 9837162450 = 13681^2 + 2129^3, count: 1268
val: 9814362750 = 523^2 + 2141^3, count: 1269
val: 9815674302 = 1259^2 + 2141^3, count: 1270
=> 1270