Как рассчитать наименьшее число с определенным количеством делителей?
От Проблема с Project Euler 500
Число делителей 120 равно 16. На самом деле 120 является наименьшим числом, имеющим 16 делителей.
Найдите наименьшее число с 2 ** 500500 делителями. Дайте свой ответ по модулю 500500507.
Достаточно просто подсчитать делители n, например. в Python len([i for i in range(1,n+1) if n % i == 0]). Это O (n).
Я попробовал поиск грубой силы и нашел наименьшее число с 32 делителями 840, но это слишком медленно для проблемы выше. Из неравенства count_divisors(n) <= n число будет массовым.
Как вы думаете? Есть идеи? Как рассчитать наименьшее число с определенным количеством делителей?
Изменить. Я не думаю, что это дубликат. Этот вопрос более конкретный, он относится к определенному классу гораздо больших чисел. другой вопрос. Его ответы не применимы к этой проблеме, это разная величина.
Ответы
Ответ 1
Вы должны использовать формулу для числа делителей целых n:
d (n) = (a 1 +1) (a 2 +1)... (a k +1)
где
n = p 1 a 1 * p 2 a 2 * p 3 a 3 *... * p k а <суб > ксуб >
является единственным представлением любого целого по степеням его простых делителей. Это хорошо известная формула, но если кто-то задается вопросом, как ее получить, обратите внимание, что d делит n тогда и только тогда, когда d имеет вид p 1 x 1 * p 2 x 2 * p 3 x 3 *... * p k x k где каждый из x i находится между 0 и i, поэтому существуют опции i + 1 для выбора каждого из x i. Теперь просто примените правило продукта, и вы получите желаемую формулу.
При фиксированном d(n) (как в вашем случае) минимальное значение n очевидно получается путем тщательного выбора полномочий существующих простых чисел или путем добавления новых простых чисел. Давайте проделаем этот простой пример, 16:
d (x) = (a 1 +1) (a 2 +1)... (a k +1) = 16 = 2 4.
Это означает, что у вас есть не более 4 разных простых чисел, поэтому:
x = 2 a 1 * 3 a 2 * 5 a 3 * 7 a 4
где a i >= 0. Вопрос теперь - чтобы получить минимальное значение x, лучше ли увеличить мощности 2 (т.е. прирастить a 1) или использовать 7 (т.е. Взять 4= 1 вместо 4= 0)? Ну, просто проверить, 2 * 3 * 5 * 7 > 2 3 * 3 * 5 = 120, поэтому ответ 120 в этом случае.
Как обобщить этот подход? Вы должны создать мини-кучу, где вы будете накладывать силы простых чисел, следя за тем, чтобы количество делителей достигло указанного значения. В случае 16 эта мини-куча будет содержать числа 2, 3, 5, 7, 2 2 3 2 2 4 и т.д.. Зачем? Потому что 16 = 2 4 поэтому каждый из (a i +1) должен делить 16, т.е. Должен быть мощностью 2. Каждый раз, когда вы добавляете новую мощность, он должен увеличить левую сторону (т.е. переменную d(x)) силой 2, так как ваша конечная цель - найти наименьшее число с 2 500500 делителями. Куча инициализируется с помощью первых k простых чисел (в заявлении проблемы, k = 500500), и на каждом шаге, когда вы набираете p x из кучи, p 2x и результат умножается на p x. Пошаговое решение для d(x)= 16 = 2 4:
Step Heap d(x) x
==========================
0 2,3,5,7 1 1
1 3,4,5,7 2 2
2 4,5,7,9 4 6
3 5,7,9,16 8 24
4 7,9,16,25 16 120
НТН.
Ответ 2
Вот высокий уровень моего Javascript - где factorCount представляет количество делителей:
- Найдите разложение простого фактора фактораCount
- Создать каждую уникальную комбинацию этих простых факторов
- Для каждой комбинации извлеките эти значения комбинации из исходного массива основных факторов и добавьте одно значение в этот массив, который является извлеченными значениями, умноженными вместе. Затем отсортируйте элементы в порядке убывания.
- Для каждого массива, созданного предыдущим шагом, проверить, что дает минимальное число при вычислении 2 ^ (b1-1) * 3 ^ (b2-1) 5 ^ (b3-1)...
- Это минимальное число, рассчитанное наименьшим числом с
factorCount числом делителей
Здесь выполняется разбиение кода моего JavaScript на высокий уровень:
var primeFactors = findPrimeFactors(factorCount);
var primeFactorCombinations = removeDuplicateArrays(generateCombinations(primeFactors, 1));
var combinedFactorCandidates = generateCombinedFactorCombinations(primeFactors, primeFactorCombinations);
var smallestNumberWithFactorCount = determineMinimumCobination(combinedFactorCandidates);
И вот полный ша-банг:
function smallestNumberByFactorCount(factorCount) {
function isPrime(primeCandidate) {
var p = 2;
var top = Math.floor(Math.sqrt(primeCandidate));
while(p<=top){
if(primeCandidate%p === 0){ return false; }
p++;
}
return true;
}
function findPrimeAfter(currentPrime) {
var nextPrimeCandidate = currentPrime + 1
while(true) {
if(isPrime(nextPrimeCandidate)){
return nextPrimeCandidate;
} else {
nextPrimeCandidate++;
}
}
}
function findPrimeFactors(factorParent) {
var primeFactors = [];
var primeFactorCandidate = 2;
while(factorParent !== 1){
while(factorParent % primeFactorCandidate === 0 && factorParent !== 1 ){
primeFactors.push(primeFactorCandidate);
factorParent /= primeFactorCandidate;
}
primeFactorCandidate = findPrimeAfter(primeFactorCandidate);
}
return primeFactors;
}
function sortArrayByValue(a,b){
return a-b;
}
function clone3DArray(arrayOfArrays) {
var cloneArray = arrayOfArrays.map(function(arr) {
return arr.slice();
});
return cloneArray;
}
function doesArrayOfArraysContainArray(arrayOfArrays, array){
var aOA = clone3DArray(arrayOfArrays);
var a = array.slice(0);
for(let i=0; i<aOA.length; i++){
if(aOA[i].sort().join(',') === a.sort().join(',')){
return true;
}
}
return false;
}
function removeDuplicateArrays(combinations) {
var uniqueCombinations = []
for(let c=0; c<combinations.length; c++){
if(!doesArrayOfArraysContainArray(uniqueCombinations, combinations[c])){
uniqueCombinations[uniqueCombinations.length] = combinations[c];
}
}
return uniqueCombinations;
}
function generateCombinations(parentArray, minComboLength) {
var generate = function(n, src, got, combinations) {
if(n === 0){
if(got.length > 0){
combinations[combinations.length] = got;
}
return;
}
for (let j=0; j<src.length; j++){
generate(n - 1, src.slice(j + 1), got.concat([src[j]]), combinations);
}
return;
}
var combinations = [];
for(let i=minComboLength; i<parentArray.length; i++){
generate(i, parentArray, [], combinations);
}
combinations.push(parentArray);
return combinations;
}
function generateCombinedFactorCombinations(primeFactors, primeFactorCombinations) {
var candidates = [];
for(let p=0; p<primeFactorCombinations.length; p++){
var product = 1;
var primeFactorsCopy = primeFactors.slice(0);
for(let q=0; q<primeFactorCombinations[p].length; q++){
product *= primeFactorCombinations[p][q];
primeFactorsCopy.splice(primeFactorsCopy.indexOf(primeFactorCombinations[p][q]), 1);
}
primeFactorsCopy.push(product);
candidates[candidates.length] = primeFactorsCopy.sort(sortArrayByValue).reverse();
}
return candidates;
}
function determineMinimumCobination (candidates){
var minimumValue = Infinity;
var bestFactorCadidate = []
for(let y=0; y<candidates.length; y++){
var currentValue = 1;
var currentPrime = 2;
for(let z=0; z<combinedFactorCandidates[y].length; z++){
currentValue *= Math.pow(currentPrime,(combinedFactorCandidates[y][z])-1);
currentPrime = findPrimeAfter(currentPrime);
}
if(currentValue < minimumValue){
minimumValue = currentValue;
bestFactorCadidate = combinedFactorCandidates[y];
}
}
return minimumValue;
}
var primeFactors = findPrimeFactors(factorCount);
var primeFactorCombinations = removeDuplicateArrays(generateCombinations(primeFactors, 1));
var combinedFactorCandidates = generateCombinedFactorCombinations(primeFactors, primeFactorCombinations);
var smallestNumberWithFactorCount = determineMinimumCobination(combinedFactorCandidates);
return smallestNumberWithFactorCount;
}
Вставьте вышеуказанный блок кода в консоль вашего браузера, и вы можете проверить его самостоятельно:
> smallestNumberByFactorCount(3) --> 4
> smallestNumberByFactorCount(4) --> 6
> smallestNumberByFactorCount(5) --> 16
> smallestNumberByFactorCount(6) --> 12
> smallestNumberByFactorCount(16) --> 120
> smallestNumberByFactorCount(100) --> 45360
> smallestNumberByFactorCount(500) --> 62370000
> smallestNumberByFactorCount(5000) --> 4727833110000
> smallestNumberByFactorCount(100000000) --> 1.795646397225103e+40
Мой алгоритм начинает шить кровать, когда входной сигнал достигает около 100 миллионов... так что для Project Euler проблема 500, где вход будет 2 ^ 500500 (действительно, действительно, действительно большой номер), вам понадобится другой подход, Тем не менее, это хороший общий подход, который приближает вас. Надеюсь, что это поможет.
Пожалуйста, оставляйте комментарии с предложениями по оптимизации эффективности. Я хотел бы услышать их.
Ответ 3
Наивысший делитель любого числа имеет, кроме самого себя, половину числа. Например, 120 имеет максимальный делитель, отличный от 60. Таким образом, вы можете легко уменьшить диапазон от (n + 1) до (n/2).
Более того, для числа, имеющего m-делителей, число должно быть по крайней мере ((m-1) * 2), следуя приведенной выше логике (-1, поскольку m-й номер сам). Например, число с 4 делителями должно быть по крайней мере 6. Итак, ваш поиск n теперь имеет меньший диапазон.
Эти два будут немного сократить время выполнения.
Ответ 4
Не полный ответ вместо некоторых подсказок:
-
максимальный целочисленный делитель n равен n/2
так что не нужно проверять все делители до n
-
можно использовать простое разложение
Максимальный простой делитель равен sqrt(n) поэтому нет необходимости проверять до n вместо этого проверять до sqrt(n) или до числа, которое имеет половину из n бит
m=(2^(ceil(ceil(log2(n))/2)+1))-1
это должно немного ускорить процесс, но вам нужно добавить вычисление не простых делителей
-
это похоже на какой-то ряд (простое разложение)
divisors | prime_divisors | non_prime_divisors | LCM(all divisors)
1 | 1 | | 1
2 | 1,2 | | 2
3 | 1,2 | 4 | 4
4 | 1,2,3 | 6 | 6
5 | 1,2 | 4,8,16 | 16
6 | 1,2,3 | 4,6,12 | 12
7 | 1,2 | 4,8,16,32,64 | 64
8 | 1,2,3 | 4,6,8,12,24 | 24
...
16 | 1,2,3,5 |4,6,8,10,12,15,20,24,30,40,60,120 | 120
поэтому постарайтесь найти уравнение, которое генерирует этот порядок, а затем просто вычислите n-th итерацию по модулю арифметики (простая операция PI... modmul). Я вижу, четные и нечетные элементы имеют отдельное уравнение...
[edit1] разложение до 16 делителей
1: 1
2: 1, 2
3: 1, 2, 4
4: 1, 2, 3, 6
5: 1, 2, 4, 8, 16
6: 1, 2, 3, 4, 6, 12
7: 1, 2, 4, 8, 16, 32, 64
8: 1, 2, 3, 4, 6, 8, 12, 24
9: 1, 2, 3, 4, 6, 9, 12, 18, 36
10: 1, 2, 3, 4, 6, 8, 12, 16, 24, 48
11: 1, 2, 4, 8, 16, 32, 64, 128, 256, 512,1024
12: 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60
13: 1, 2, 4, 8, 16, 32, 64, 128, 256, 512,1024,2048,4096
14: 1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 48, 64, 96, 192
15: 1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 36, 48, 72, 144
16: 1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60, 120
Ответ 5
Как объясняет Мильен Микич, функция подсчета делителей определяется простой факторизацией. Чтобы вычислить n, начните с 1 и используйте жадный алгоритм, чтобы удвоить количество делителей k раз, выбирая самый дешевый коэффициент на каждом шаге. Первоначальные затраты - это простые числа, замененные их квадратом, когда вы их используете. После предварительного вычисления первых k простых чисел вы можете сделать это быстро с помощью мини-кучи. В Python
import primesieve # pip install primesieve
import heapq
def solve(k, modulus=None):
"""Calculate the smallest number with 2**k divisors."""
n = 1
costs = primesieve.generate_n_primes(k) # more than necessary
for i in range(k):
cost = heapq.heappop(costs)
heapq.heappush(costs, cost**2)
n *= cost
if modulus:
n %= modulus
return n
assert solve(4) == 120
if __name__ == "__main__":
print(solve(500500, 500500507))
Ответ 6
Фу, я просто решил это в java. Мое "наименьшее число с 2 ^ n дивизорами" оказалось представлено как карта простых чисел и их полномочий.
Эта головоломка так же оптимистична, как и все: получите свой код, а затем реорганизуйте его. Это определенно стоит проверить примерно до 2 ^ 30 делителей, так как есть место для всех видов ошибок второго порядка, которые могут срабатывать при оптимизации. Повторно используйте результаты предыдущих вычислений, старайтесь не сортировать что-либо, и прекратите итерацию, как только сможете (NavigableSet и LinkedHashMap были полезны). Я не собираюсь учить мою бабушку эффективно проверять на прочность.
Я использовал java долго всюду, но с числами такого размера легко пройти Long.MAX_VALUE в середине вычисления, помните: (A ^ 2 * B)% C = (A * ((A * B )% C))% C.
Надеюсь, что все это мотивирует, а не отдает игру. Продолжайте!
Ответ 7
Это мой код. Вы можете использовать сито для генерации простых чисел. Если у вас есть какие-либо предложения к моему коду, пожалуйста, предложите.
def findfactors(num):
list1=[]
for i in range(num,1,-1):
if num%i==0:
list1.append(i)
return list1
def getcombinations(num):
factors=findfactors(num)
list1=[]
if num==1:
return 1
for i in factors:
if getcombinations(num//i)!=1:
list1.append([i,getcombinations(num//i)])
else:
list1.append(i)
return list1
def unloadlist(list1):
list2=[]
if type(list1).__name__=="list":
for i in list1[1]:
if type(i).__name__=="list":
i=unloadlist(i)
if type(i).__name__=="list":
flag=True
for j in i:
if type(j).__name__=="list":
list2.append([list1[0]]+j)
flag=False
if flag==True:
list2.append([list1[0]]+i)
else:
list2.append([list1[0],i])
if len(list2)==1:
list2=list2[0]
else:
list2=list1
return list2
def mergeitems(list1):
list2=[]
for i in list1:
if type(i).__name__=="int":
list2.append((i,))
elif type(i).__name__=="list":
if type(i[0]).__name__!="list":
list2.append(tuple(sorted(i,reverse=True)))
else:
for j in i:
list2.append(tuple(sorted(j,reverse=True)))
set1=set(list2)
return set1
def find_smallest_number(num):
#start writing your code here
list1=getcombinations(num)
for i in range(0,len(list1)):
list1[i]=unloadlist(list1[i])
mainlist=mergeitems(list1)
possibles=[]
primes=[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227]
for i in mainlist:
num=1
for j in range(0,len(i)):
num*=primes[j]**(i[j] - 1)
possibles.append(num)
return min(possibles)
num=7
print("The number of divisors :",num)
result=find_smallest_number(num)
print("The smallest number having",num," divisors:",result)
Ответ 8
Полностью функциональный код.
def find_smallest_number(num):
number2=0
if(num%8==0):
number2=min(2**((num/4)-1)*3**1*5**1 , 2**((num//2)-1)*3**1)
elif(num%9==0):
number2=2**((num/9)-1)*3**2*5**2
elif(num%2==0 and num%3==0):
number2=2**((num/6)-1)*3**2*5**1
elif((num%4==0)):
number2=2**((num/4)-1)*3**1*5**1
elif(num%2==0):
number2=2**((num/2)-1)*3**1
else:
number2=2**(num-1)
return number2
num=32
print("The number of divisors :",num)
result=find_smallest_number(num)
print("The smallest number having",num," divisors:",result)
