Eccoci.

Distinct Primes Factors

ℹ️Published on Friday, 4th July 2003, 06:00 pm; Solved by 63743;
Difficulty rating: 5%

Problem 47

The first two consecutive numbers to have two distinct prime factors are:

$$ \begin{align} 14 &= 2 \times 7\\ 15 &= 3 \times 5. \end{align}$$

The first three consecutive numbers to have three distinct prime factors are:

$$ \begin{align} 644 & = 2^2 \times 7 \times 23\\ 645 & = 3 \times 5 \times 43\\ 646 & = 2 \times 17 \times 19. \end{align} $$

Find the first four consecutive integers to have four distinct prime factors each. What is the first of these numbers?

Soluzione

Partiamo caricando la libreria necessaria e creando una semplice funzione di supporto che filtri i fattori del numero \(n\). Questi, dato che ci interessa vedere se due numeri hanno fattori diversi, intesi come coppia fattore primo \(p\) elevato ad un certo esponente \(k\), li salviamo proprio come calcolo di \(p^k\). Così ad esempio distinguiamo facilmente, in un unico cconfronto, che \(2^2\) è un fattore diverso da \(2^3\).

using Primes
function factor_terms(n)
	dict=factor(n)
	return keys(dict) .^ values(dict)
end
@show factor_terms(14)
@show factor_terms(15)
@show factor_terms(644)
@show factor_terms(645)
@show factor_terms(646)

factor_terms(14) = [2, 7]
factor_terms(15) = [3, 5]
factor_terms(644) = [4, 7, 23]
factor_terms(645) = [3, 5, 43]
factor_terms(646) = [2, 17, 19]

Per la soluzione, scorriamo sui numeri interi, salviamo nella variabile s i fattori degli ultimi 4 consecutivi, e su questi effettuiamo il controllo dei requisiti:

1. ogni numero deve avere 4 divisori e

2. tutti i divisori devono essere diversi

Il controllo sull'essere diversi lo facciamo con un Set, un insieme nel senso matematico del termine, che quindi filtra via valori se ne incontra dei duplicati.

s = []
i = 100
found = 0
@time while found != 1
	push!(s,factor_terms(i))
	if length(s) == 5
		# quando s contiene 5 elementi togliamo il primo,
		# per tenere gli ultimi 4 come quelli nuovi consecutivi che indaghiamo
		popfirst!(s)
	end
	if length.(s) == [4,4,4,4] && length(Set(vcat(s...))) == 16
		println("Soluzione: ", collect(i-3:i))
		println("I loro fattori sono: ", s)
		global found = 1
	end
	global i += 1
end

Soluzione: [134043, 134044, 134045, 134046]
I loro fattori sono: Any[[3, 7, 13, 491], [4, 23, 31, 47], [5, 17, 19, 83], [2, 9, 11, 677]]
  0.463976 seconds (3.14 M allocations: 127.738 MiB, 4.21% gc time, 54.79% compilation time)