Calcul efficace du plus petit entier avec n diviseurs

9

Afin de résoudre ce problème, j'ai d'abord observé que

ϕ(p1e1 p2e2 pkek)=(e1+1)(e2+1)(ek+1)

Où est le nombre de diviseurs (pas nécessairement premiers) de . Si est le plus petit entier tel que , alorsϕ(m)mmϕ(m)=n

ϕ(m)=n
(e1+1)(e2+1)(ek+1)=n

Maintenant, nous devons choisir ei telle sorte que ipiei soit minimal. Les choix pour p sont triviaux - ce ne sont que les nombres premiers dans l'ordre croissant.

Cependant, ma première pensée pour choisir ei était incorrecte. Je pensais que vous pouviez simplement factoriser n , trier les facteurs dans l'ordre décroissant et soustraire 1. La plupart du temps, cela fonctionne bien, par exemple le plus petit entier avec n=15 diviseurs est:

15=53
15=(4+1)(2+1)
m=2432=144

Mais ceci est incorrect pour n=16 :

16=2222
16=(1+1)(1+1)(1+1)(1+1)
m=21315171=210

Alors que la bonne réponse est:

m = 2 3 3 1 5 1 = 120

16=(3+1)(1+1)(1+1)
m=233151=120

Il est donc clair que nous devons parfois fusionner des facteurs. Dans ce cas, car . Mais je ne vois pas exactement une stratégie de fusion claire et directe. Par exemple, on pourrait penser que nous devons toujours fusionner dans le pouvoir, mais ce n'est pas vrai: 271>222

m = 2 96 3 1 5 1 7 1 11 1 > 2 96 3 3 5 5 1 7 1

1552=(96+1)(1+1)(1+1)(1+1)(1+1)
m=296315171111>296335171

Je ne peux pas immédiatement penser à un exemple, mais mon instinct dit que certaines approches gourmandes peuvent échouer si elles fusionnent d'abord les mauvais pouvoirs.

Existe-t-il une stratégie optimale simple pour fusionner ces pouvoirs pour obtenir la bonne réponse?


Addenda. Un algorithme gourmand qui vérifie chaque fusion possible et effectue la meilleure fusion par fusion, échoue sur . La série de fusions un par un est la suivante:n=3072

22315171111131171191231291311

23325171111131171191231291

25335171111131171191231

Cependant, la solution optimale est:

27335271111131171191
orlp
la source
@orlp: Ma suggestion était: corriger (disons, ) et corriger (disons, ). Ensuite, vous essayez de minimiser , sous réserve de . Ainsi, en travaillant avec un nombre fixe (de nombres premiers), vous pouvez ignorer les complications de savoir si un certain nombre premier doit apparaître dans le minimum global ou non. Vous trouvez le minimum pour chaque , puis prenez le min de ceux-ci. 24 m 2 k 1 log ( 2 ) + k 2 log ( 3 ) k 1 k 2 = 24 m mn24m2k1log(2)+k2log(3)k1k2=24mm
Steve D

Réponses:

1

Voici une solution, basée sur mes commentaires ci-dessus. Je ne prétends pas que c'est optimal.

L'idée est de considérer , que nous définissons comme "le plus petit entier positif avec exactement diviseurs et facteurs premiers distincts". Nous faisons les observations faciles:n mT(n,m)nm

T(n,1)=2n1T(2m,m)=p1p2pm

Et nous avons aussi la récurrence:

T(n,m)=mind|n[T(nd,m1)pmd1]

Enfin, la quantité que vous recherchez est

min1ilog(n)T(n,i)

À cette fin, voici du code Python, qui correspond à tous les chiffres que vous avez donnés ci-dessus. Notez que cela fonctionne avec les logarithmes pour garder les nombres plus petits: ainsi l'entier réel que vous recherchez est round(2**smallest(n)).

import functools
import itertools
import math

# All primes less than 100.
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,
]

LOG_PRIMES = [math.log2(p) for p in PRIMES]

def smallest(n):
  max_factors = math.ceil(math.log2(n))
  min_so_far = float('Infinity')
  factors = factorize(n)
  memo = {}
  for i in range(1, max_factors+1):
    t = T(n,i, factors, memo)
    if 0.0 < t < min_so_far:
      min_so_far = t
  return min_so_far

def T(n, m, factors=None, memo=None):
  if memo is None:
    memo = {}
  if n < 2 or m < 1:
    return 0
  elif m == 1:
    # Everything on the smallest prime.
    return (n-1) * LOG_PRIMES[0]
  elif n < 2**m:
    return 0
  elif n == 2**m:
    # Product of first m primes, in log.
    return sum(LOG_PRIMES[:m])
  elif (n,m) in memo:
    return memo[(n,m)]

  if factors is None:
    factors = factorize(n)
  if len(factors) < m:
    return 0

  smallest = float('Infinity')  
  for factor_list in powerset(factors):
    divisor = product(factor_list)
    first = T(divisor, m-1, factor_list, memo)
    # No such product.
    if first < 1.0:
      continue
    second = (n/divisor - 1) * LOG_PRIMES[m-1]
    total = first + second
    if total < smallest:
      smallest = total

  memo[(n,m)] = smallest
  return smallest

def product(nums):
  return functools.reduce(lambda x,y: x*y, nums, 1)

def factorize(n):
  prime_factors = []
  for p in PRIMES:
    while n%p == 0:
      n //= p
      prime_factors.append(p)
    if n == 1:
      break
  return prime_factors

def powerset(lst):
  # No empty set.
  return itertools.chain.from_iterable(itertools.combinations(lst, r) 
                                       for r in range(1, len(lst)+1))
Steve D
la source
Les commentaires auxquels vous faites référence semblent avoir été supprimés malheureusement, mais cela est certainement optimal (dans le sens de calculer le plus petit entier possible avec exactement facteurs). Est-ce l'optimalité de la complexité temporelle dont vous n'êtes pas sûr? Je ne connais pas de limite étroite pour le nombre de diviseurs d'un entier , mais même avec la limite très pessimiste de votre algorithme n'est que , qui devrait être assez rapide pour dans les dizaines de milliers! (BTW: J'écrivais le même algorithme (moins quelques optimisations) mais vous y êtes arrivé en premier, bravo!)n O ( n ) O ( n 2 log n ) nnnO(n)O(n2logn)n
j_random_hacker
@j_random_hacker: Oui, je ne sais pas ce qui est arrivé à ces commentaires: ils étaient nombreux, et ils sont maintenant tous partis! Je parlais en effet de la complexité du temps; En fait, je pense qu'il est probablement plus proche de , mais le nombre de diviseurs est une fonction délicate. Bien sûr, le code ci-dessus peut certainement être mieux optimisé: ne tient pas compte des doublons, par exemple. O(nlogn)powerset
Steve D
Je pense que c'est plus facile à implémenter efficacement en utilisant la programmation dynamique: gist.github.com/orlp/0fbb7784782712bc7c411aa58a188143 Je ne suis vraiment pas à l'aise avec le truc du logarithme en passant - une précision limitée en virgule flottante va à un moment donné viser des choses. Cela étant dit, je ne pense pas que ce soit plus rapide que de générer toutes les partitions multiplicatives. En fait, je crois que c'est exactement ce qu'il fait déguisé!
orlp
Après avoir lu le commentaire de @ orlp et votre code de plus près, je pense maintenant qu'il est important que la complexité temporelle (et les performances pratiques) changent for factor_list in powerset(factors)en quelque chose qui génère chaque diviseur distinct d' nune seule fois. De cette façon, pour, disons, , si l' on considère des solutions contenant exactement les premiers nombres premiers comme les facteurs premiers distincts, vous ne le faire travail non récursive au lieu de , qui est exponentiel en . 2 k O ( k 2 ) O ( ( 2 kn=2k3k2kO(k2)kO((2kk))k
j_random_hacker
1
@orlp: J'ai mal compris le terme "partitions multiplicatives", désolé. Merci pour le code Python. Pour voir pourquoi l'algorithme de Steve D n'est pas parallèle à ce code, considérez multiplicative_partitions(24)ce qui produit (entre autres) les partitions [4, 3, 2]et [6, 2, 2], qui (après avoir inversé l'ordre afin de donner au plus petit facteur premier l'exposant le plus élevé) correspondent aux solutions et , respectivement. L'algorithme de Steve D ne considérera jamais cette dernière solution, car il a déjà déterminé que la sous-solution . 2332512531512332=72<2531=96
j_random_hacker
-1

Les candidats possibles pour le "plus petit entier avec n diviseurs" sont les entiers de la forme où a ≥ b ≥ c ... et (a + 1) (b + 1) (c + 1) ... = n.2a·3b·5c...

Vous devez donc trouver toutes les façons d'exprimer n comme le produit d'entiers ≥ 2 dans un ordre non croissant, et calculer et vérifier les candidats correspondants. Par exemple, lorsque n = 16, 16 = 8 · 2 = 4 · 4 = 4 · 2 · 2 = 2 · 2 · 2 · 2, les possibilités sont donc de , , , , et le plus petit est .27·323·3323·3·52·3·5·723·3·5=120

Si n est le produit de deux nombres premiers p · q, p ≥ q, les seuls candidats sont et , et ce dernier est toujours plus petit .2pq12p1·3q1

Vous pouvez comprendre une condition où il pourrait y avoir un facteur par exemple, en vérifiant si pour certains x premier qui n'est pas un facteur. Dans l'exemple n = 16, il y a un facteur car .2ab12ab1>2a1·xb12323<2·7

gnasher729
la source
3
Pardonnez-moi, mais cela ne répond pas du tout à ma question, cela résume simplement ce que j'ai trouvé dans ma question. Le titre n'est que cela: un titre, pas la question elle-même. J'ai l'impression que vous n'avez lu que le titre avant de répondre. La vraie question se trouve au bas du texte de ma question.
orlp
C'est répondu dans le dernier paragraphe.
gnasher729
@ gnasher729 C'est loin d'être une réponse à une question "calculer efficacement", ou même pour "une stratégie optimale de fusion"
yo '26