J'ai vérifié le nombre de taxis avec Ruby

Le deuxième d'une série de vérifications de nombres mystérieux avec Ruby! (Combien de fois cela continuera-t-il?)

Cliquez ici pour le 1er précédent ↓ J'ai vérifié avec Ruby s'il y avait un nombre capreca dans un entier dans une certaine plage

Cette fois, c'est ** nombre de taxis **. Comme la dernière fois, j'ai reçu le matériel de Youtube.

"Maths et physique universitaires" appris à l'école préparatoire Familier avec l'épisode de génie de Ramanujan [Nombre de taxis]

Quel est le nombre de taxis

Le nième numéro de taxi (désigné par numéro de taxi, Ta (n) ou Taxicab (n)) est le plus petit nombre positif représenté de n façons comme la somme de ** deux nombres cubiques **. Défini comme un entier de. Le nom «nombre de taxis» vient d'un épisode dans lequel Shrinivasa Ramanujan a souligné que c'était Ta (2) pour le numéro de taxe 1729 que Hardy avait pris.

Source: Wikipedia

** Le numéro légal ** est un nombre qui est le cube d'un certain nombre **. Puisque le nombre carré est au carré, c'est un système évolutif.

スクリーンショット 2020-07-04 18.31.02.png

Et le nombre de taxis semble s'exprimer de plusieurs manières par la somme des chiffres législatifs (addition)

Je l'ai cherché

Contenu: Le plus petit entier positif représenté de n façons par x ^ 3 + y ^ 3 (y compris la sortie de la combinaison de x, y) Condition: (1 ≤ x ≤ y ≤ 500)

taxi.rb


def safe_invert(orig_hash)
  orig_hash.each_key.group_by { |key| orig_hash[key] }.sort.to_h
end

hash = {}

(1..500).each do |y|
  (1..500).each do |x|
    hash.store([x, y], x ** 3 + y ** 3)
    if x == y
      break
    end
  end
end

taxi = []
n = 1

safe_invert(hash).each do |k, v|
  if v.size == n
    taxi.push("Ta(#{n}) => #{k}: #{v}")
    n += 1
  end
end

puts taxi
Ta(1) => 2: [[1, 1]]
Ta(2) => 1729: [[9, 10], [1, 12]]
Ta(3) => 87539319: [[255, 414], [228, 423], [167, 436]]

Le nombre minimum qui peut être exprimé de trois manières comme la somme des chiffres législatifs est déjà de 87,53 millions, ce qui est un nombre assez élevé.

Description du code

Je vais vous expliquer pas à pas Essayons de réduire la gamme pour plus de simplicité

Condition: (1 ≤ x ≤ y ≤ 5)

taxu.rb


hash = {}

(1..5).each do |y|
  (1..5).each do |x|
    hash.store([x, y], x ** 3 + y ** 3)
  end
end

p hash
{[1, 1]=>2, [2, 1]=>9, [3, 1]=>28, [4, 1]=>65, [5, 1]=>126,
[1, 2]=>9, [2, 2]=>16, [3, 2]=>35, [4, 2]=>72, [5, 2]=>133,
[1, 3]=>28, [2, 3]=>35, [3, 3]=>54, [4, 3]=>91, [5, 3]=>152,
[1, 4]=>65, [2, 4]=>72, [3, 4]=>91, [4, 4]=>128, [5, 4]=>189,
[1, 5]=>126, [2, 5]=>133, [3, 5]=>152, [4, 5]=>189, [5, 5]=>250}

Tout d'abord, donnez "x" et "y" un entier de 1 à 5.

Regardons la réponse (somme), qui est la somme des nombres au cube, et ajoutons-la à hash. La méthode store de la classe Hash est une méthode qui ajoute un élément avec key comme premier argument et valeur comme second argument.

Il y a 5 x 5 = 25 longueurs différentes pour hash.

スクリーンショット 2020-07-04 18.43.14.png

Comme vous pouvez le voir dans le tableau, la réponse que vous obtenez en échangeant x et y est la même. La réponse est «133» à la fois quand »(x, y) = (2, 5)« et quand »(x, y) = (5, 2)». Cela ne compte pas comme deux façons. Il y a un moyen. C'est donc cette gamme qu'il faut retrouver dans le tableau

スクリーンショット 2020-07-04 18.57.40.png

Donc, si «x» et «y» sont identiques, ajoutez un élément à «hash» et «break» pour rompre la boucle.

taxu.rb


hash = {}

(1..5).each do |y|
  (1..5).each do |x|
    hash.store([x, y], x ** 3 + y ** 3)
    if x == y
      break
    end
  end
end

p hash
{[1, 1]=>2,
[1, 2]=>9, [2, 2]=>16,
[1, 3]=>28, [2, 3]=>35, [3, 3]=>54,
[1, 4]=>65, [2, 4]=>72, [3, 4]=>91, [4, 4]=>128,
[1, 5]=>126, [2, 5]=>133, [3, 5]=>152, [4, 5]=>189, [5, 5]=>250}

Puis la seconde moitié En particulier, l'intérieur de la méthode est compliqué.

Dans le hachage, la clé contenait un tableau de «[x, y]» et la valeur contenait un élément de «somme des nombres légaux». Passer par la méthode safe_invert créera un hachage avec la clé et la valeur inversées, en tenant compte de la duplication.

taxi.rb


def safe_invert(orig_hash)
  orig_hash.each_key.group_by { |key| orig_hash[key] }.sort.to_h
end

p safe_invert(hash)
{2=>[[1, 1]], 9=>[[1, 2]], 16=>[[2, 2]], 28=>[[1, 3]], 35=>[[2, 3]],
54=>[[3, 3]], 65=>[[1, 4]], 72=>[[2, 4]], 91=>[[3, 4]], 126=>[[1, 5]],
128=>[[4, 4]], 133=>[[2, 5]], 152=>[[3, 5]], 189=>[[4, 5]], 250=>[[5, 5]]}

each_key.group_by { |key| orig_hash[key] }Avec chaque clé comme valeur, ʻOrig_hash [clé] `(c'est-à-dire valeur) est la clé pour créer un hachage. Inversion de la valeur clé.

C'est une idée difficile, mais j'y ai fait référence Hash # invert (Manuel de référence de Ruby 2.7.0)

Et comme il est trié par ordre croissant de clé avec sort et en même temps il est converti en tableau, Revenir au hachage avec .to_h.

Je pense que le mérite de ce traitement n'est pas mis en évidence lorsque «x, y» est 1 à 5. Si vous étendez la plage de 1 à 12 pour que ** 1729 **, qui est Ta (2), apparaisse, le résultat de sortie ressemblera à ceci ...

{ ......, 1729=>[[9, 10], [1, 12]], ......}

Vous pouvez voir que la longueur du tableau de valeurs est maintenant de deux, et il existe deux façons de l'exprimer comme la somme des 1729 nombres législatifs.

taxi.rb


taxi = []
n = 1

safe_invert(hash).each do |k, v|
  if v.size == n
    taxi.push("Ta(#{n}) => #{k}: #{v}")
    n += 1
  end
end

puts taxi

Avec ʻeachpour le dernier hachage Ajoutez la première correspondance de la longueur du tableau de valeurs de 1 au tableau videtaxi` Sortez le résultat et terminez.

De côté

J'ai découvert en regardant Wikipedia Ta (4) n'apparaîtra que si la plage est étendue de ** 1 à 19000 **.

J'ai essayé de l'exécuter avec (1..19000), Même après avoir attendu quelques minutes, le processus ne s'est pas terminé et j'ai abandonné.

Après tout, Ruby peut ne pas convenir à une vérification exhaustive: transpiration:

Si vous avez une meilleure façon de l'écrire, faites-le nous savoir dans les commentaires!

** (Ajouté le 05/07/2020) ** Vous avez suggéré une version améliorée dans les commentaires!

Recommended Posts

J'ai vérifié le nombre de taxis avec Ruby
J'ai vérifié la partie de java.net.URL # getPath
Gérez la version de Ruby elle-même avec rbenv
J'ai essayé DI avec Ruby
[Ruby] Questions et vérification du nombre d'arguments de méthode
J'ai brièvement résumé la grammaire de base de Ruby
[Ruby] Je souhaite inverser l'ordre de la table de hachage
Trouvez le nombre de jours dans un mois avec Kotlin
À propos du comportement de ruby Hash # ==
J'ai lu la source de ArrayList que j'ai lu
Programmation avec ruby (en route)
J'ai lu la source d'Integer
J'ai lu la source de Long
Impressions de faire Black Jack-cli avec Ruby
J'ai lu la source de Short
J'ai lu la source de Byte
[Ruby] Afficher le contenu des variables
J'ai vérifié l'outil de création automatique de tests unitaires (version fin 2019)
J'ai essayé de créer un environnement de serveur UML Plant avec Docker
J'ai vérifié car la réponse était étrange lors du débogage avec Tomcat 8
[Illustration] Recherche de la somme des pièces avec une fonction récursive [Ruby]
Je veux changer la valeur de l'attribut dans Selenium of Ruby
Créez un grand nombre d'enregistrements avec une seule commande à l'aide du fichier seeds.rb Ruby on Rails
J'ai essayé d'exprimer les résultats avant et après de la classe Date avec une ligne droite numérique
J'ai essayé d'utiliser Ruby pour voir s'il y a un nombre capreca dans un entier dans une certaine plage
J'ai vérifié la bibliothèque "junit-quickcheck" qui peut effectuer des tests basés sur les propriétés avec JUnit.
Vérifiez le contenu des paramètres avec le levier
J'ai étudié le traitement interne de Retrofit
Comment déterminer le nombre de parallèles
[Ruby] Génération de nombres aléatoires à 4 chiffres avec sprintf
J'ai examiné le flux de communication TCP avec Spring Integration (édition client)
J'ai examiné le flux de communication TCP avec Spring Integration (édition serveur)
[Ruby] Coupez le contenu des publicités Twitter
J'ai fait une mort risquée avec Ruby
J'ai essayé de résoudre le problème de la séquence Tribonacci en Ruby, avec récurrence.
Extraire une partie d'une chaîne en Ruby
J'ai essayé d'utiliser pleinement le cœur du processeur avec Ruby
À propos du traitement de BigDecimal (avec réflexion)
J'ai essayé de visualiser l'accès de Lambda → Athena avec AWS X-Ray
À propos du nombre de threads de Completable Future
J'étais coincé avec la gestion des fuseaux horaires lors du formatage avec SimpleDateFormat
Mettre en forme le contenu de LocalDate avec DateTimeFormatter
[Java] Vérifiez le nombre d'occurrences de caractères
J'ai essayé de mesurer et de comparer la vitesse de Graal VM avec JMH
Après tout, je voulais prévisualiser le contenu de mysql avec Docker ...
Comment insérer un traitement avec n'importe quel nombre d'éléments dans le traitement itératif dans Ruby
J'ai essayé de comparer la technologie d'infrastructure des ingénieurs ces jours-ci avec la cuisine.
Je l'ai utilisé sans connaître la cartographie O / R des rails, donc je l'ai vérifié.
Spécialiste de la sécurité de l'automne 2017 J'ai vérifié la fréquence des mots qui apparaissaient le matin 2
Comment trouver la cause de l'erreur Ruby
[Ruby] Résumé des définitions de classe. Maîtrisez les bases.