_{(via le chat )}

L'entrée OEIS A123321 répertorie la séquence de nombres qui sont le produit de sept nombres premiers distincts. Par souci de concision, nous appellerons cela un numéro 7DP . Les premiers nombres et leurs diviseurs correspondants sont ci-dessous:

510510 = 2 * 3 * 5 * 7 * 11 * 13 * 17
570570 = 2 * 3 * 5 * 7 * 11 * 13 * 19
690690 = 2 * 3 * 5 * 7 * 11 * 13 * 23
746130 = 2 * 3 * 5 * 7 * 11 * 17 * 19

Le défi ici sera de trouver le nombre 7DP le plus proche, en termes de distance absolue, d'une entrée donnée.

Contribution

Un seul entier positif n dans n'importe quel format pratique .

Production

Le numéro 7DP le plus proche de n , encore une fois dans n'importe quel format pratique. Si deux numéros 7DP sont liés pour le plus proche, vous pouvez sortir l'un ou les deux.

Règles

• Les nombres peuvent être supposés correspondre au [int]type de données par défaut de votre langue (ou équivalent).
• Un programme complet ou une fonction sont acceptables.
• Les failles standard sont interdites.
• Il s'agit de code-golf , donc toutes les règles de golf habituelles s'appliquent et le code le plus court l'emporte.

Exemples

5 -> 510510
860782 -> 870870
1425060 -> 1438710 (or 1411410, or both)

Python, 89 86 85 octets

f=lambda n,k=0:126^sum(1>>n%i<<7*(n/i%i<1)for i in range(2,n))and f(n+k,k%2*2+~k)or n

L'algorithme est O (effrayant) pour commencer et la récursivité n'aide pas vraiment, mais il fonctionne bien tant que n est suffisamment proche d'un nombre 7DP.

Merci à @xnor d'avoir joué au golf sur 3 octets!

Testez - le sur repl.it .

Comment ça fonctionne

Python n'a pas de primalité ou de factorisation intégrée, mais nous pouvons identifier les nombres 7DP par la quantité et la nature de leurs diviseurs.

Par le principe de multiplication, le nombre de diviseurs d'un entier peut être calculé comme le produit des exposants incrémentés de sa factorisation première. Ainsi, σ ₀ (n) ( fonction de diviseur ) vaut 2 ^m chaque fois que n est un nombre mDP.

σ ₀ (n) = 128 est donc une condition nécessaire, mais elle n'est pas suffisante; par exemple, σ ₀ (2 ¹²⁷ ) = 128 , mais 2 ¹²⁷ n'est clairement pas un nombre 7DP. Cependant, si σ ₀ (n) = 128 et qu'aucun carré parfait ne divise n également, alors n est un nombre 7DP.

Pour l'entrée n , l'algorithme consiste à inspecter les entiers n , n - 1 , n + 1 , n - 2 , n + 2 , etc. et à renvoyer le premier qui est un nombre 7DP.

Lorsque f est appelé avec l'argument n , les événements suivants se produisent:

• Le code

  126^sum(1>>n%i<<7*(n/i%i<1)for i in range(2,n))

  teste si n n'est pas un nombre 7DP comme suit.

  Pour tous les entiers i tels que 1 <i <n , 1>>n%i<<7*(n/i%i<1)est évalué.

  • Si n est divisible par i mais pas par i ² , 1>>n%idonne 1 et (n/i%i<1)donne 0 , ce qui donne
    1 · 2 ^{7 · 0} = 1 .

  • Si n est divisible par i ² , 1>>n%iet les (n/i%i<1)deux donnent 1 , ce qui donne 1 · 2 ^{7 · 1} = 128 .

  • Si n n'est pas divisible par i , 1>>n%idonne 0 , ce qui donne 0 · 2 ^{7 · x} = 0 .

  
  La somme des nombres entiers résultants sera 2 ^m - 2 si n est un nombre MDP (ses 2 ^m de diviseurs, à l' exclusion 1 et n ) et un plus grand nombre de de 127 , si n a un facteur carré parfait. Ainsi, la somme sera 126 si et seulement si n est un nombre 7DP.

• Pour les nombres 7DP, la somme est 126 , donc XOR avec 126 donne 0 , ce qui est faux. Ainsi, la ou la partie du lambda est exécutée et f renvoie la valeur actuelle de n .

• Si n n'est pas un nombre 7DP, XOR renverra une valeur véridique non nulle. Ainsi, la partie et de la lambda est exécutée.

  f(n+k,k%2*2+~k)

  appelle récursivement f avec des valeurs mises à jour de n (le prochain nombre potentiel 7DP) et k (la différence entre le nouveau candidat et celui qui suit).

  Si k est un entier pair non négatif, k%2*2donne 0 et ~kdonne - (k + 1) . La somme des deux résultats est - (k + 1) , qui est un entier impair impair qui est supérieur de 1 en valeur absolue à k .

  Si k est un entier impair impair, k%2*2donne 2 et ~kdonne - (k + 1) . La somme des deux résultats est 2 - (k + 1) = - (k - 1) , qui est un entier pair non négatif qui est 1 unité supérieur en valeur absolue à k .

  Cela signifie que k prend les valeurs 0, -1, 2, -3, 4, ⋯ .

  Lorsqu'ils sont ajoutés cumulativement à n ₀ (la valeur initiale de n ), les entiers résultants sont

  • n ₀ + 0
  • ( n ₀ + 0) - 1 = n ₀ - 1
  • ( n ₀ - 1) + 2 = n ₀ + 1
  • ( n ₀ + 1) - 3 = n ₀ - 2
  • ( n ₀ - 2) + 4 = n ₀ + 2
  • etc.

  
  assurant que le premier numéro de 7DP que nous rencontrons est aussi proche de n ₀ que possible.

Brachylog , 44 40 16 octets

_{Biffé 44 est toujours régulier 44; (}

:I=+.>0,.$pPdPl7

Exemple:

?- run_from_atom(':I=+.>0,.$pPdPl7',1425060,Z).
Z = 1438710 .

Se pourrait-il que cette langue ne suce pas toujours? J'ai battu Jelly et MATL!

Le cas de test avec 5est le plus long et prend environ 10 secondes sur ma machine.

Ce serait 12 octets s'il $pn'était pas buggé (nous n'aurions pas besoin de la >0,.partie)

Explication

Brachylog utilise la programmation logique par contrainte par défaut pour toute l'arithmétique entière. De plus, l'étiquetage intégré =fonctionne sur des domaines éventuellement infinis.

Il unifie successivement une variable sans contraintes (dans (-inf, inf)) en tant que tels: 0, 1, -1, 2, -2, 3, ….

Par conséquent, nous pouvons obtenir le numéro 7DP le plus proche en recherchant le premier numéro Iunifié dans (-inf, inf)(à l'aide du retour automatique), qui Input + Iest un numéro 7DP.

:I=                Label variables in [Input, I]. I has no constraints and Input is known
   +.              Unify Output with Input + I
     >0,           Output > 0 (wouldn't be needed if $p failed for numbers less than 1)
        .$pP       Unify P with the list of prime factors of Output
            dP     Check that P with duplicates removed is still P
              l7   Check that the length of P is 7

Gelée, 17 octets

Pµạ³,
×⁹ÆRœc7Ç€ṂṪ

Fonctionne en théorie, mais prend plusieurs années.

Voici une version qui fonctionne réellement pour les entrées données, mais échoue théoriquement pour les grandes entrées:

Pµạ³,
50ÆRœc7Ç€ṂṪ

Essayez-le ici. Cela génère tous les nombres premiers jusqu'à 50, puis trouve toutes les 7 combinaisons de nombres premiers dans cette liste, puis tous leurs produits. Enfin, il trouve simplement l'élément le plus proche de cette liste à l'argument donné.

Bien sûr, une fois que nos 7DP contiennent des nombres premiers supérieurs à 50, cela échouera. La version théorique génère tous les nombres premiers jusqu'à 256n pour une entrée n , mais fonctionne autrement de la même manière.

Preuve

Soit p(x)le premier prime suivant x. Une limite supérieure (extrêmement lâche) pour le produit 7DP le plus proche de x est:

p(x) * p(p(x)) * p(p(p(x))) * ... * p(p(p(p(p(p(p(x)))))))

Il nous suffit donc de vérifier les nombres premiers dans [2… p (p (p (p (p (p (p (x)))))))]] . Le postulat de Bertrand dit que p (x) ≤ 2x , il suffit donc de vérifier tous les nombres premiers jusqu'à 128x .

MATL , 21 17 16 14 13 octets

Merci à Dennis pour une suggestion qui a supprimé 4 octets, et une autre qui a sauvé 1 octet de plus!

t17*Zq7XN!pYk

Cela fonctionne en théorie, mais manque de mémoire pour les entrées ci-dessus 6(compilateur en ligne).

Une version plus efficace utilise 21 octets et calcule tous les cas de test en environ une seconde:

t3e4/k16+_YqZq7XN!pYk

Essayez-le en ligne!

• Version à mémoire insuffisante
• Version économe en mémoire
• Version économe en mémoire, tous les cas de test

Explication

Version économe en mémoire

Prenez l'entrée N = 860782comme exemple. Il suffit de considérer les nombres premiers à M = 29, qui est le premier premier que multiplié par 2*3*5*7*11*13excède N . Dans cet exemple 2*3*5*7*11*13*29 = 870870,. Le premier prime est 31. Tout produit impliquant que le premier ou plus sera au moins 2*3*5*7*11*13*31 = 930930, et il est donc garanti pas être la solution, car elle dépasse ce 870870qui est supérieur à N .

M est calculé comme le premier nombre premier supérieur à max(N/(2*3*5*7*11*13), 16). La maxfonction est utilisée pour s'assurer qu'au moins 17est sélectionné. Pour économiser quelques octets, le code remplace 2*3*5*7*11*13 = 30030par 30000et fonctionne maxpar addition. Ces modifications sont valides car elles donnent une valeur plus élevée.

t      % Take input implicitly. Duplicate
3e4/k  % Divide input by 30000 and round down (rounding here is only needed
       % due to a bug in the "next prime" function)
16+    % Add 16
_Yq    % Next prime
Zq     % Prime numbers up to that value
7XN    % Combinations of those primes taken 7 at a time. Gives a 2D array
       % with each combination on a different row
!p     % Product of each row
Yk     % Output product that is closest to the input. Implicitly display

Version à mémoire insuffisante

Pour réduire davantage le nombre d'octets, la division peut être supprimée; en fait, il suffit de multiplier par 17(merci, @Dennis). Cela garantit que le prochain nombre premier est inclus (par le postulat de Bertrand ) et que le résultat est au moins 17. Cela fonctionne en théorie, mais manque de mémoire pour des entrées plus grandes qu'environ 6.

Dans le code, la section

3e4/k  % Divide input by 30000 and round down (rounding here is only needed
       % due to a bug in the "next prime" function)
16+    % Add 16
_Yq    % Next prime

est remplacé par

17*    % Multiply by 17

Pyke, 32 octets

#PDl 7q.ID}lRlqi*(#)DF-X,)R],She

Essayez-le ici!

Notez que cela ne fonctionne pas en ligne - cela arrive à expiration. Cette version ne vérifie que 2 nombres premiers distincts et devrait fonctionner plus rapidement. Lorsqu'il y a 2 numéros de la même distance de la cible, il choisit celui du bas.

Cela passe par tous les nombres jusqu'à ce qu'il en trouve un qui soit plus grand que l'entrée et qui soit un 7DP. Pour chaque numéro, il s'en débarrasse s'il ne s'agit pas d'un 7DP. Il a ensuite une liste de 7DP jusqu'à l'entrée avec un plus grand. Il sélectionne ensuite celui qui est le plus proche de l'entrée.

Julia, 59 octets

!n=sort(map(prod,combinations(17n|>primes,7))-n,by=abs)[]+n

C’est très inefficace, mais cela fonctionne pour le premier cas de test en pratique et pour les autres en théorie.

Au prix de 5 octets supplémentaires - pour un total de 64 octets - l'efficacité peut être considérablement améliorée.

!n=sort(map(prod,combinations(n>>14+17|>primes,7))-n,by=abs)[]+n

Essayez-le en ligne!

Contexte

Comme mentionné dans la réponse de @ LuisMendo , l'ensemble des nombres premiers que nous devons considérer pour le nombre 7DP le plus proche est assez petit. Il suffit que l'ensemble contienne un nombre 7DP plus grand que l'entrée n , ce qui sera vrai si et seulement s'il contient un nombre premier p ≥ 17 tel que 30300p = 2 · 3 · 5 · 7 · 11 · 13 · p ≥ n .

Dans l'intervalle contenant au moins un nombre premier prouve que l'intervalle [x, 1,5x) contient au moins un nombre premier chaque fois que x ≥ 8 . Depuis 30030/16384 ≈ 1,83 , cela signifie qu'il doit être un nombre premier p à (n / 30030, n / 16384) à chaque fois que n> 8 · 30.300 = 242.400 .

Enfin, lorsque n <510510 , p = 17 est clairement suffisant, il suffit donc de considérer les nombres premiers jusqu'à n / 16384 + 17 .

Au détriment de l'efficacité, nous pouvons plutôt considérer des nombres premiers jusqu'à 17n . Cela fonctionne lorsque n = 1 et est largement supérieur à n / 16384 + 17 pour des valeurs plus grandes de n .

Comment ça fonctionne

17n|>primeset n>>14+17|>primes(le décalage de bits équivaut à la division par 2 ¹⁴ = 16384 ) calculer les plages premières mentionnées dans le paragraphe précédent. Ensuite, combinations(...,7)calcule tous les tableaux de sept nombres premiers différents dans cette plage, et le mappage prodsur ceux-ci calcule leurs produits, c'est-à-dire les nombres 7DP à partir desquels nous choisirons la réponse.

Ensuite, -nsoustrayez n prom chaque numéro 7DP, puis triez sort(...,by=abs)ces différences par leurs valeurs absolues. Enfin, nous sélectionnons la première différence avec []et calculons le nombre 7DP correspondant en ajoutant n avec+n .

Pyth, 30 octets

L&{IPbq7lPby#.W!syMH,hhZa0teZ,

Essayez-le en ligne!

Suite de tests.

(5 prend trop de temps à courir)

Explication

L&{IPbq7lPby#.W!syMH,hhZa0teZ,

L&{IPbq7lPb     Defines a function y, whose argument is b:
 &                  Return if both the following are true:
  {IPb                  the prime factorization contains no duplicate; and:
      q7lPb             the number of prime factors is 7

           y#.W!syMH,hhZa0teZ,   The main programme. Input as Q.
                             ,QQ Implicit arguments, yield [Q,Q].
             .W                  While
               !syMH                   both numbers do not satisfy y:
                    ,hhZ             increment the first number
                          teZ        and decrement the second number
                        a0           while making it non-negative.

Mathematica 136 80 75 octets

Il s'agit d'une approche simple, allant de l'extérieur n .

nest un produit à 7 nombres premiers distincts si le nombre de facteurs premiers est 7 ( PrimeNu@#==7) et aucun de ces facteurs n'apparaît plus d'une fois ( SquareFreeQ@#&).

g@n_:=(k=1;While[!(PrimeNu@#==7&&SquareFreeQ@#&)⌊z=n-⌊k/2](-1)^k⌋,k++];z)

Ma communication antérieure (136 octets) a trouvé à la fois le premier produit 7-prime-prime ci n- dessus et, s'il existe, le premier 7-distinct-prime product ci-dessous n. Il a ensuite simplement déterminé ce qui était le plus proche n. Si les produits étaient équidistants, il retournait les deux.

La version actuelle vérifie n-1, n + 1, n-2, n + 2 ... jusqu'à ce qu'elle atteigne le premier produit 7-prime-prime. Cette version plus efficace adopte l'approche adoptée par Dennis.

L'avancée clé consistait à utiliser ⌊k/2](-1)^k⌋pour renvoyer la série, 0, 1, -1, 2, -2 ... Le zéro est utilisé pour vérifier s'il ns'agit lui-même d'un produit à 7 nombres distincts. Pour cette raison, Floor(c'est-à-dire ⌊...⌋) est utilisé à la place de Ceiling.

g[5]
g[860782]
g[1425060]

510510

870870

1438710

05AB1E , 10 octets

°Åp7.ÆPs.x

Essayez-le en ligne!

Essaie toutes les combinaisons de 7 des 10 premiers nombres premiers d'entrée **. Manque de mémoire pour les entrées supérieures à 1.

Version 14 octets considérablement plus efficace:

5°/7+Åp7.ÆPs.x

Essayez-le en ligne!

Utilise les premiers nombres premiers (entrée / 100000 + 7).