P41

Pandigital Prime

Problem 41

We shall say that an $n$-digit number is pandigital if it makes use of all the digits $1$ to $n$ exactly once. For example, $2143$ is a $4$-digit pandigital and is also prime.

What is the largest $n$-digit pandigital prime that exists?

Soluzione

Lavoriamo con i numeri primi quindi intanto carichiamo la libreria per avere la comoda funzione isprime(n)

using Primes

Fatto ciò, l'idea credo sia semplice: dato che ci interessa il massimo numero che soddisfa il criterio (essere primo e pandigitale) possiamo scorrere sui numeri dall'alto verso il basso, in modo da fermarci subito quando incontriamo il primo che funziona. Per ottimizzare il calcolo però ci accorgiamo che ci sono vari modi per verificare se un numero è pandigitale:

Ordiniamo le cifre del numero e controlliamo se corrispondono a quelle da 1 a $n$, dove $n$ è la lunghezza del numero stesso

function ispandigital_v1(n)
	return sort(digits(n)) == collect(1:length(string(n)))
end
@show ispandigital_v1(1234)
@show ispandigital_v1(1235)

ispandigital_v1(1234) = true
ispandigital_v1(1235) = false

Ordiniamo ancora il numero ma espandiamo con un loop il controllo sulla singola cifra uguale a quella attesa (prima cifra uguale a 1, seconda uguale a 2, ecc). Dovrebbe essere un po' più efficiente della precedente versione perché qui non allochiamo un altro vettore, quello creato con collect(1:length(string(n)))

function ispandigital_v2(n)
	v = sort(digits(n))
	for i in 1:length(v)
		if v[i] != i
			return false
		end
	end
	return true
end
@show ispandigital_v2(1234)
@show ispandigital_v2(1235)

ispandigital_v2(1234) = true
ispandigital_v2(1235) = false

In queste versioni successive eliminiamo il fatto di dover ordinare le cifre del numero, dato che la funzione sort potrebbe essere un po' costosa, ed effettuiamo il controllo salvandoci, nelle celle $i$-esime del vettore seen, quante volte incontriamo la cifra $i$-esima. Se la cifra è uguale a zero o l'abbiamo già incontrata, allora il numero non sarà pandigitale.

function ispandigital_v3(n; verbose=false)
    len = 0
    seen = falses(9)
    while n > 0
        digit = n % 10
        n ÷= 10
        if digit == 0 || seen[digit]
            return false
        end
        seen[digit] = true
        len += 1
		if verbose
			println("digit = $digit, seen = ", join(Int.(seen)))
		end
    end
	return len+1 == findfirst(x -> x==0, seen)
end
@show ispandigital_v3(123467, verbose=true)
@show ispandigital_v3(123444, verbose=true)
@show ispandigital_v3(123654, verbose=true)

digit = 7, seen = 000000100
digit = 6, seen = 000001100
digit = 4, seen = 000101100
digit = 3, seen = 001101100
digit = 2, seen = 011101100
digit = 1, seen = 111101100
ispandigital_v3(123467, verbose = true) = false
digit = 4, seen = 000100000
ispandigital_v3(123444, verbose = true) = false
digit = 4, seen = 000100000
digit = 5, seen = 000110000
digit = 6, seen = 000111000
digit = 3, seen = 001111000
digit = 2, seen = 011111000
digit = 1, seen = 111111000
ispandigital_v3(123654, verbose = true) = true

Quest'ultima versione ha la stessa logica della precedente ma anziché salvarsi il controllo "visto/non visto" in una cella di un vettore (il seen di prima), stavolta usiamo un numero, digits_mask, le cui singole cifre 0/1 si salvano l'esito di tale controllo, e questo dovrebbe ottimizzare tutto dato che non allochiamo della memoria aggiuntiva. Per farlo, quando incontriamo la cifra $i$ possiamo salvare l'averla incontrata tramite un OR tra la maschera corrente il numero ottenuto shiftando 1 a sinistra $i$ volte. E come prima, se la cifra $i$ è uguale a zero o l'abbiamo già incontrata allora il numero non sarà pandigitale.

function ispandigital_v4(n; verbose=false)
    len = 0
    digits_mask = 0
    while n > 0
        digit = n % 10
        n ÷= 10
        if digit == 0 || (digits_mask & (1 << digit)) != 0
            return false
        end
        digits_mask |= (1 << digit)
        len += 1
		if verbose
			println("digit = $digit, mask = ", bitstring(digits_mask)[end-9:end-1])
		end
    end
    return digits_mask == (1 << (len + 1)) - 2
end
@show ispandigital_v4(123467, verbose=true)
@show ispandigital_v4(123444, verbose=true)
@show ispandigital_v4(123654, verbose=true)

digit = 7, mask = 001000000
digit = 6, mask = 001100000
digit = 4, mask = 001101000
digit = 3, mask = 001101100
digit = 2, mask = 001101110
digit = 1, mask = 001101111
ispandigital_v4(123467, verbose = true) = false
digit = 4, mask = 000001000
ispandigital_v4(123444, verbose = true) = false
digit = 4, mask = 000001000
digit = 5, mask = 000011000
digit = 6, mask = 000111000
digit = 3, mask = 000111100
digit = 2, mask = 000111110
digit = 1, mask = 000111111
ispandigital_v4(123654, verbose = true) = true

Facciamo ora un piccolo test di performance

using BenchmarkTools
pan_no = 123947076
@btime ispandigital_v1(pan_no)
@btime ispandigital_v2(pan_no)
@btime ispandigital_v3(pan_no)
@btime ispandigital_v4(pan_no)

  156.079 ns (7 allocations: 416 bytes)
  99.126 ns (4 allocations: 256 bytes)
  42.807 ns (3 allocations: 96 bytes)
  18.811 ns (0 allocations: 0 bytes)
false

pan_yes = 123467895
@btime ispandigital_v1(pan_yes)
@btime ispandigital_v2(pan_yes)
@btime ispandigital_v3(pan_yes)
@btime ispandigital_v4(pan_yes)

  160.528 ns (7 allocations: 416 bytes)
  105.448 ns (4 allocations: 256 bytes)
  58.430 ns (3 allocations: 96 bytes)
  27.005 ns (0 allocations: 0 bytes)
true

e arriviamo quindi con la quarta versione alla soluzione del problema.

@time for i in 987654321:-2:2
	if ispandigital_v4(i) && isprime(i)
		@show i
		break
	end
end

i = 7652413
  4.593506 seconds (9 allocations: 264 bytes)

Last modified: August 18, 2025. Website built with Franklin.jl and the lovely Julia programming language.

Eccoci.

Pandigital Prime

Problem 41

Soluzione