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.

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.

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

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!