Calcul des cousins ​​Collatz

21

Définissez la fonction f (n) pour un entier positif n comme suit:

  • n / 2 , si n est pair
  • 3 * n + 1 , si n est impair

Si vous appliquez à plusieurs reprises cette fonction à tout n supérieur à 0, le résultat semble toujours converger vers 1 (bien que personne n'ait encore pu le prouver). Cette propriété est connue sous le nom de conjecture de Collatz .

Définissez le temps d'arrêt d' un entier comme le nombre de fois que vous devez le passer par la fonction Collatz f avant qu'il n'atteigne 1. Voici les temps d'arrêt des 15 premiers entiers:

1  0
2  1
3  7
4  2
5  5
6  8
7  16
8  3
9  19
10 6
11 14
12 9
13 9
14 17
15 17

Appelons n'importe quel ensemble de numéros avec les mêmes cousins ​​Collatz de temps d'arrêt . Par exemple, 5 et 32 ​​sont des cousins ​​Collatz, avec un temps d'arrêt de 5.

Votre tâche: écrire un programme ou une fonction qui prend un entier non négatif et génère l'ensemble des cousins ​​Collatz dont le temps d'arrêt est égal à cet entier.

Contribution

Un entier non négatif S, donné via STDIN, ARGV ou un argument de fonction.

Production

Une liste de tous les numéros dont le temps d' arrêt est S, triée en ordre croissant ordre. La liste peut être sortie par votre programme, ou retournée ou sortie par votre fonction. Le format de sortie est flexible: séparé par des espaces, séparé par des sauts de ligne ou par tout autre format de liste standard de votre langue, tant que les chiffres sont facilement distinguables les uns des autres.

Exigences

Votre soumission doit donner des résultats corrects pour tout S ≤ 30. Elle doit se terminer en quelques secondes ou minutes, et non en heures ou jours.

Exemples

0  -> 1
1  -> 2
5  -> 5, 32
9  -> 12, 13, 80, 84, 85, 512
15 -> 22, 23, 136, 138, 140, 141, 150, 151, 768, 832, 848, 852, 853, 904, 906, 908, 909, 5120, 5376, 5440, 5456, 5460, 5461, 32768

Voici un résumé de la sortie pour S = 30 .

C'est le : le programme le plus court en octets gagne. Bonne chance!

DLosc
la source
Et les cycles? Je n'ai vu aucune mention d'évitement de cycle. Parce que pour S = 5, il y a 3 valeurs [4, 5, 32] parce que vous pouvez aller "1 - 2 - 4 - 1 - 2- 4"
JPMC
1
@JPMC L'évitement de cycle est impliqué par la définition du temps d'arrêt. Le temps d'arrêt de 4 est 2, pas 5, car 2 est "le nombre de fois que vous devez le passer par la fonction Collatz avant qu'il n'atteigne 1."
DLosc
Ah, pardonne-moi. Je pensais qu'un nombre pourrait avoir plusieurs temps d'arrêt, car plusieurs chemins peuvent y conduire. Mais cela concernait la construction à partir de 1, ne fonctionnant pas à partir de N. Désolé à ce sujet.
JPMC
1
@DLosc Pyth, bien sûr.
isaacg

Réponses:

7

Pyth, 26 24 21 octets

Su+yMG-/R3fq4%T6G1Q]1

Ce code s'exécute instantanément pour S=30. Essayez-le vous-même: Démonstration

Merci à @isaacg pour avoir économisé 5 octets.

Explication

Mon code commence par 1et annule la fonction Collatz. Il mappe tous les numéros dde l' S-1étape vers 2*det (d-1)/3. Le dernier n'est pas toujours valable cependant.

                        implicit: Q = input number
                   ]1   start with G = [1]
 u                Q     apply the following function Q-times to G:
                          update G by
   yMG                      each number in G doubled
  +                       +
          fq4%T6G           filter G for numbers T, which satisfy 4==T%6
       /R3                  and divide them by 3
      -          1          and remove 1, if it is in the list
                            (to avoid jumping from 4 to 1)
S                       sort the result and print
Jakube
la source
C'est une belle utilisation de -F.
isaacg
1
Si vous mettez un - ... 1autour de la somme à l'intérieur de la réduction, vous n'avez pas besoin que la réduction soit un .u, ni à l' -Fextérieur. Enregistre 2 caractères.
isaacg
@isaacg Merci. J'avais en fait cela dans une version précédente, mais je l'ai supprimé lors du débogage d'une erreur.
Jakube
3
J'ai emprunté @ isaacg pour ma propre réponse. J'ai passé des heures à essayer de trouver le code le plus court pour supprimer les doublons, mais c'est de loin la solution la plus élégante. Aussi, j'aime vraiment l'utilisation d'un tuple pour éliminer les quotients invalides. Malheureusement, CJam n'a pas de tuples, mais j'ai réussi à mapper les quotients invalides à 1.
Dennis
@Jakube q4%d6est équivalent à !%hhd6, mais 1 caractère plus court.
isaacg
8

Mathematica, 98 92 89 octets

Cette solution résout S = 30immédiatement:

(p={0};l={1};Do[l=Complement[##&@@{2#,Mod[a=#-1,2]#~Mod~3~Mod~2a/3}&/@l,p=p⋃l],{#}];l)&

Il s'agit d'une fonction sans nom prenant Scomme seul paramètre et renvoyant une liste des cousins ​​Collatz.

L'algorithme est une simple recherche en largeur. Les cousins ​​Collatz pour une donnée Ssont tous les entiers qui peuvent être atteints à partir des cousins ​​Collatz pour S-1via 2*nou des nombres impairs qui peuvent être atteints via (n-1)/3. Nous devons également nous assurer que nous ne produisons que les entiers qui ont été atteints pour la première fois après les Sétapes, afin de garder une trace de tous les cousins ​​précédents pet de les supprimer du résultat. Comme nous le faisons de toute façon, nous pouvons économiser quelques octets en calculant les étapes de tous les cousins ​​précédents (pas seulement ceux de S-1) pour enregistrer quelques octets (ce qui le rend légèrement plus lent, mais pas sensiblement pour le nécessaire S).

Voici une version légèrement plus lisible:

(
  p = {0};
  l = {1};
  Do[
    l = Complement[
      ## & @@ {2 #, Mod[a = # - 1, 2] #~Mod~3~Mod~2 a/3} & /@ l,
      p = p ⋃ l
    ]~Cases~_Integer,
    {#}
  ];
  l
) &
Martin Ender
la source
5

Python 2, 86 83 75 73 71 octets

f=lambda n,k=1:sorted([k][n:]or(k>4==k%6and f(n-1,k/3)or[])+f(n-1,k*2))

Appelez comme f(30). n = 30est à peu près instantané.

(Merci à @DLosc pour l'idée de récurrence en kétant un nombre plutôt qu'une liste de cousins, et quelques octets. Merci à @isaacg d'avoir abandonné ~-.)

Cette variante est beaucoup plus courte, mais prend malheureusement trop de temps en raison d'une ramification exponentielle:

f=lambda n,k=1:sorted([k][n:]or(k>4==k%6)*f(n-1,k/3)+f(n-1,k*2))
Sp3000
la source
Intéressant - ma solution originale est très similaire, mais (prenant des optimisations couple de la vôtre) sort 2 octets plus court: f=lambda d,n=1:d and sorted(sum((c(d-1,x)for x in[n*2]+[~-n/3][:n>4==n%6]),[]))or[n]. Il est moins efficace avec les appels de fonction mais le fait toujours n = 30en moins d'une seconde.
DLosc
1
@DLosc J'ai aimé votre idée et je l'ai améliorée :)
Sp3000
Agréable! Voici 2 octets de plus:f=lambda n,k=1:sorted([k][n:]or(k>4==k%6and f(n-1,~-k/3)or[])+f(n-1,k*2))
DLosc
@DLosc Ahaha merci. Je jure toujours qu'il doit y avoir un meilleur moyen de court-circuiter cependant ...
Sp3000
Je pense que ce ~-n'est pas nécessaire parce que vous utilisez la division entière.
isaacg
5

CJam, 29 26 octets

Xari{{2*_Cmd8=*2*)}%1-}*$p

Nous remercions @isaacg pour son idée de supprimer les 1 après chaque itération, ce qui m'a fait économiser deux octets directement et un autre indirectement.

Essayez-le en ligne dans l' interpréteur CJam (devrait se terminer en moins d'une seconde).

Comment ça marche

Xa       e# Push A := [1].
ri{      e# Read an integer from STDIN and do the following that many times:
  {      e# For each N in A:
    2*   e#     Push I := (N * 2) twice.
    _Cmd e#     Push (I / 12) and (I % 12).
     8=  e#     Push K := (I % 12 == 8).

         e#     (K == 1) if and only if the division ((N - 1) / 3) is exact and
         e#     yields an odd integer. In this case we can compute the quotient 
         e#     as (I / 12) * 2 + 1.

    *2*) e#     Push J := (I / 12) * K * 2 + 1.

         e#     This yields ((N - 1) / 3) when appropriate and 1 otherwise.
  }%     e# Replace N with I and J.
  1-     e# Remove all 1's from A.

         e# This serves three purposes:

         e# 1. Ones have been added as dummy values for inappropriate quotients.

         e# 2. Not allowing 1's in A avoids integers that have already stopped
         e#    from beginning a new cycle. Since looping around has been prevented,
         e#    A now contains all integers of a fixed stopping time.

         e# 3. If A does not contain duplicates, since the maps N -> I and N -> J
         e#      are inyective (exluding image 1) and yield integers of different
         e#      parities, the updated A won't contain duplicates either.

}*       e#
$p       e# print(sort(C))
Dennis
la source
4

CJam, 35 octets

1]ri{_"(Z/Y*"3/m*:s:~\L+:L-_&0-}*$p

Explication à venir. Il s'agit d'une version beaucoup plus rapide que l'approche "assez simple" (voir dans l'historique des modifications).

Essayez-le en ligne ici pour N = 30lequel s'exécute en quelques secondes sur la version en ligne et instantanément dans le compilateur Java

Optimiseur
la source
Combien de temps cela prendra-t-il pour les entrées plus importantes? It should finish in seconds or minutes, not hours or days.
DLosc
Ah, je vois. La version Python que j'ai écrite semblait prendre environ 5 heures pour N = 30.
DLosc
La dernière version fonctionne presque instantanément.
Optimizer
6
Il y a un bug dans votre code. Le cas de test S=15ne fonctionne pas.
Jakube
3

Java 8, 123

x->java.util.stream.LongStream.range(1,(1<<x)+1).filter(i->{int n=0;for(;i>1;n++)i=i%2<1?i/2:3*i+1;return n==x;}).toArray()

Quand xest 30, le programme prend 15 minutes et 29 secondes.

Étendu

class Collatz {
    static IntFunction<long[]> f =
            x -> java.util.stream.LongStream.range(1, (1 << x) + 1).filter(i -> {
                int n = 0;
                for (; i > 1; n++)
                    i = i % 2 < 1 ? i / 2 : 3 * i + 1;
                return n == x;
            }).toArray();

    public static void main(String[] args) {
        System.out.println(Arrays.toString(f.apply(15)));
    }
}
Ypnypn
la source
Juste curieux, combien de temps cela prend-il pour S = 30?
Geobits
Cela ne fonctionne que dans Java 8, correct? L'utilisation javac 1.7.0_79sur Ubuntu m'a donné beaucoup d'erreurs de syntaxe.
DLosc
@DLosc Correct; Je mentionnerai cela dans le post.
Ypnypn
Restreindre la condition du terminal de boucle à i > 1 && ++n <= x(vous pouvez n++également la supprimer ) semble être encore plus rapide pour seulement 5 caractères de plus ... environ 3 minutes pour S = 30 pour moi. Cela se réduit en moins d'une minute en toute sécurité si .parallel()
j'inclus
1

Python 2, 118 octets

Eh bien, je me suis dit que je n'atteindrais pas le meilleur score Python après avoir vu la solution de @ Sp3000. Mais cela ressemblait à un petit problème amusant, donc je voulais quand même essayer une solution indépendante:

s={1}
for k in range(input()):
 p,s=s,set()
 for t in p:s.add(2*t);t>4and(t-1)%6==3and s.add((t-1)/3)
print sorted(s)

Même chose avant de supprimer les espaces:

s={1}
for k in range(input()):
    p,s=s,set()
    for t in p:
        s.add(2 * t)
        t > 4 and (t - 1) % 6 == 3 and s.add((t - 1) / 3)
print sorted(s)

Il s'agit d'une implémentation très directe d'une première recherche étendue. À chaque étape, nous avons l'ensemble avec le temps d'arrêtk , et dérivons l'ensemble avec le temps d'arrêt k + 1en ajoutant les prédécesseurs possibles de chaque valeur tdans l'ensemble de l'étape k:

  • 2 * t est toujours un prédécesseur possible.
  • Si tpeut s'écrire 3 * u + 1, où uest un nombre impair qui n'est pas1 , alors uest également un prédécesseur.

Il faut environ 0,02 secondes pour fonctionner N = 30sur mon MacBook Pro.

Reto Koradi
la source
En général, ce s.add(x)n'est pas nécessaire dans un golf car vous pouvez généralement le faire à la s|={x}place. En outre, en utilisant ~-xau lieu d' (x+1)enregistre sur les crochets. Mais sinon, bon travail :)
Sp3000
@ Sp3000 Merci. Je ne peux pas facilement remplacer la seconde s.add()car elle devient une affectation et ne peut plus faire partie de l'expression. Cela fonctionne pour le premier. Les forboucles basées sur des compteurs sont toujours aussi assez verbeuses. Je pensais que je pouvais le raccourcir en utilisant une whileboucle, mais il s'est avéré être exactement le même et la même longueur.
Reto Koradi
Au lieu d'une forboucle, puisque vous n'utilisez pas l'entrée d'une autre manière, vous pouvez probablement le faire à la exec"..."*input()place :)
Sp3000
1

PHP 5.4+, 178 octets

La fonction

function c($s,$v=1,$p=[],&$r=[]){$p[]=$v;if(!$s--){return$r[$v][]=$p;}c($s,$v*2,$p,$r);is_int($b=($v-1)/3)&!in_array($b,$p)&$b%2?c($s,$b,$p,$r):0;ksort($r);return array_keys($r);}

Test et sortie

echo "0 - ".implode(',',c(0)).PHP_EOL;
// 0 - 1
echo "1 - ".implode(',',c(1)).PHP_EOL;
// 1 - 2
echo "5 - ".implode(',',c(5)).PHP_EOL;
// 5 - 5,32
echo "9 - ".implode(',',c(9)).PHP_EOL;
// 9 - 12,13,80,84,85,512
echo "15 - ".implode(',',c(15)).PHP_EOL;
// 15 - 22,23,136,138,140,141,150,151,768,832,848,852,853,904,906,908,909,5120,5376,5440,5456,5460,5461,32768

S (30) s'exécute en 0,24 seconde * , renvoie 732 éléments. Un couple sont

86,87,89,520,522,524,525,528, [ ... ] ,178956928,178956960,178956968,178956970,1073741824

* Pour économiser sur les octets, j'ai dû ajouter ksortet array_keysà chaque étape. Le seul autre choix que j'avais était de faire une petite fonction wrapper qui appelle c()puis appelle array_keyset ksortsur le résultat une fois. Mais en raison du temps encore décemment accrocheur, j'ai décidé de prendre le coup de performance pour un faible nombre d'octets. Sans un tri et un traitement appropriés, le temps est en moyenne de 0,07 seconde pour S (30).

Si quelqu'un a des moyens intelligents d'obtenir le traitement approprié une seule fois sans trop d'octets supplémentaires, faites-le moi savoir! (Je stocke mes numéros sous forme de clés de tableau, d'où l'utilisation de array_keyset ksort)

JPMC
la source
0

Langage C

#include <stdio.h>
#include <limits.h>    
const int s = 30;

bool f(long i)
{
    int r = 0;
    for(;;)
        if (i < 0 || r > s) return false;
        else if (i == 1) break;
        else{r ++;i = i % 2 ? 3*i + 1 : i/2;}
    return (r==s);
}

void main(){
    for(long i = 1; i < LONG_MAX; i++) if (f(i)) printf("%ld ", i);
}
venteux
la source
5
Bonjour et bienvenue chez PPCG! Comme il s'agit d'une compétition de golf par code , vous voudrez rendre votre code aussi court que possible. Veuillez également inclure le nom de la langue dans votre message.
Alex A.
Vous pouvez {}appuyer sur le bouton pour formater votre code, ce que j'ai fait pour vous. Mais comme le dit Alex, veuillez ajouter le nom de la langue (C?) Et essayez de jouer au golf :) Mais bienvenue!
Sp3000
@ Sp3000 merci d'avoir aidé à formater le code
venteux
La fonction fne se comporte pas correctement. Avec s=5, j'obtiens un tas de résultats incorrects. if (r == s)return true;devrait être return (r==s), car fne reviendra pas de façon significative quand (r < s). En outre, je pense que vous devez déclarer ien ftant que long, car il débordera assez rapidement pour certaines valeurs.
Dennis
@Dennis merci :) ça devrait êtrereturn (r==s);
venteux