Moyen le plus rapide pour filtrer la séquence A010784
https://stackoverflow.com/questions/5838716
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
La séquence A010784 à OEIS est la séquence ne contenant que des nombres à chiffres distincts. Ce montant est fini.
Ce que j'ai essayé de faire est de trouver plusieurs numéros dans cette séquence avec certains attributs.
Par exemple: 6 est un nombre distinct de magnitude 10. Cela peut être trouvé comme suit:
- 6 x 1 = 6
- 6 x 2 = 12
- 6 x 3 = 18
- 6 x 4 = 24
- 6 x 5 = 30
- 6 x 6 = 36
- 6 x 7 = 42
- 6 x 8 = 48
- 6 x 9 = 54
- 6 x 10 = 60
- 6 x 11 = 66 (deux six;. Ce ne sont pas les deux chiffres distincts)
Maintenant, je suis en train les chiffres les plus élevés disponibles pour plusieurs grandeurs de l'ordre.
Disons que toutes les commandes de 1 à 20.
Ce que je suis en train de faire est la boucle du nombre distinct le plus élevé possible, ce qui est 9876543210 et le plus grand nombre unique de magnitude 1, à un nombre très faible.
Cette méthode se sent très inefficace. Au moins, pour moi, il fait.
Je suis assez sûr que je me manque des trucs sur l'affacturage qui devrait être en mesure de rendre les choses beaucoup plus vite.
def unique_num(num):
# Check whether number is unique.
return Boolean
def unique_num_magnitude(num):
# Check of which magnitude the unique number is
return Integer
# Dictionary with the current highest values
# for each magnitude.
values = {1: 987654321...}
# Set limits
upper_limit = 9876543210
lower_limit = 1
for numbers in range(upper_limit, lower_limit, -1):
unique = unique_num(num) # Boolean
if (unique):
magnitude = unique_num_magnitude(num)
if (values[magnitude] < num):
values[magnitude] = num
La solution
Bien sûr, il y a une meilleure façon. Vous devez construire les chiffres en bas, à savoir si un nombre a1 ... ak (ce sont des chiffres k) ne sont pas de grandeur N de sorte qu'un chiffre apparaît deux fois dans les premiers k chiffres du résultat pour toute 2..n multiplicande alors ni est tout b1 nombre ... bm a1 ... ak. Ceci fournit une procédure d'énumération plus rapide catégoriquement récursif parce qu'il coupe une quantité exponentielle de l'espace de recherche loin. Détails à titre d'exercice à l'OP.
Explication plus:
On suppose qu'il existe une procédure
magnitude(number_str)
qui calcule l'amplitude de la number_str de nombre représenté dans 10 la base, de sorte que la procédure retourne 0 si number_str contient au moins une double occurrence d'un chiffre, 1 si number_str a chaque chiffre distinct mais en multipliant le nombre par deux résultats en un chiffre se produisant plusieurs fois, etc.
Cette procédure peut être mise en œuvre en termes d'un autre
unique_digits(number_str)
qui retourne vrai si tous les chiffres dans number_str sont uniques, sinon false.
Maintenant magnitude peut être mis en œuvre comme
magnitude(number_str):
n = str_to_int(number_str)
k = n
i = 0
while (unique_digits(int_to_str(k))):
k = k + n
i = i + 1
return i
Maintenant cette procédure de magnitude peut être modifié à un nocarry_magnitude qui change la vérification subtilement:
nocarry_magnitude(number_str, limit):
l = length(number_str)
assert (l > 0)
n = str_to_int(number_str)
k = n
i = 0
while (unique_digits(right_substring(int_to_str(k), l))):
k = k + n
i = i + 1
if (i == limit):
break
return i
Cette procédure vérifie pour les plusieurs fois les chiffres ne se produisent en autant de chiffres (chiffres les plus à droite ordre le plus bas) du produit dans la boucle comme il y avait des chiffres dans l'entrée d'origine. Un paramètre de limite est nécessaire pour assurer que la procédure se termine comme il est possible que la procédure fonctionne dans une boucle infinie autrement. Il est clair que pour toute s chaîne, il soutient que
magnitude(s) <= nocarry_magnitude(s, M) for large M
Par exemple, le numéro de prendre 19:
19 * 1 = 19
19 * 2 = 38
19 * 3 = 57
19 * 4 = 76
19 * 5 = 95
19 * 6 = 114 // magnitude("19") = 5
19 * 7 = 133 // nocarry_magnitude("19", 100) = 6
Qu'est-ce que je l'ai écrit ci-dessus dans la description courte est que si
nocarry_magnitude(s, x) == k for x > k
alors pour toute chaîne de caractères qui est obtenue en faisant suivre son s (désignent ce par x + s ci-dessous), il estime que
x : string of digits
magnitude(x + s) <= nocarry_magnitude(x + s, m) <= nocarry_magnitude(s, m)
when m >= magnitude(x + s)
La première inégalité vient de la revendication ci-dessus et le second est évident à partir de la définition de nocarry_magnitude. Notez que grandeur (x + s) <= magnitude (s) est un non-théorème en général, comme le montre
magnitude( "56") = 1 // 56 * 2 = 112
magnitude("256") = 12 // the first duplicate occurs at 3328
qui est causée par le report. nocarry_magnitude ne tient pas compte du report qui est la raison pour laquelle le suffixe d'une chaîne a toujours aussi grand NOCARRY grandeur que toute extension de celui-ci (vers la gauche, à savoir les chiffres d'ordre supérieur).
Maintenant vous pouvez écrire une procédure nettement plus rapide récursif comme cela pour la recherche de nombres avec une amplitude au moins M:
search(str):
if (str != ""):
int n = nocarry_magnitude(str, M)
if (n < M):
return # the optimization
int k = magnitude(str)
if (k >= M):
store_answer(str)
for d in ['1', '2', '3', '4', '5', '6', '7', '8', '9',
'10', '20', '30', '40', '50', '60', '70', '80', '90']:
search(d + str)
search("")
Voici une mise en œuvre complète Python (recherche de magnitude 36):
def unique_digits(s):
r = (len(list(s)) == len(set(s)))
return r
def magnitude(s):
n = int(s)
k = n
assert n > 0
i = 0
while (unique_digits(str(k))):
k = k + n
i = i + 1
return i
def nocarry_magnitude(s, limit):
l = len(s)
assert l > 0
n = int(s)
assert n > 0
k = n
i = 0
while (unique_digits(str(k)[-l:])):
k = k + n
i = i + 1
if (i >= limit):
break
return i
M = 36
def search(s):
if (not(s == "")):
n = nocarry_magnitude(s, M)
if (n < M):
return
k = magnitude(s)
if (k >= M):
print "Answer: %s |" % s,
i = int(s)
k = i
n = 1
while (n <= M):
print k,
k = k + i
n = n + 1
print
for d in ['1', '2', '3', '4', '5', '6', '7', '8', '9',
'10', '20', '30', '40', '50', '60', '70', '80', '90']:
search(d + s)
search("")
Et voici une course qui prend moins d'une seconde; ce trouve la réponse « 27 », qui semble être le numéro unique qui fournit l'ampleur record 36:
Answer: 27 | 27 54 81 108 135 162 189 216 243 270 297 324 351 378 405
432 459 486 513 540 567 594 621 648 675 702 729 756 783
810 837 864 891 918 945 972
Autres conseils
est-ce pas seulement un problème de permutation? Pour une grandeur donnée M faites-vous 10CM.
Par exemple, de magnitude 2, combien de façons sont là pour choisir 2 chiffres de 0..9? (En fait, il devrait être l'un de 1..9 et un de 0..9 où le deuxième chiffre ne correspond pas à la première.)
Vous ne avez certainement pas besoin de courir à travers eux tous et les vérifier. Il suffit de mettre en place un ensemble et choisir un, puis choisir un autre. Mieux encore, il suffit de les créer à partir de zéro. Tout d'abord faire tout ce qui commence par une (10, 12, 13, 14, etc.), puis tout ce qui commence par 2, etc.
Vous avez deux problèmes:
1) l'itération sur la séquence de A010784.
Utilisez itertools.permutations pour générer des nombres possibles successifs.
2) Calcul de l'amplitude d'un nombre.
Vous pouvez déterminer si un numéro ne comporte que des chiffres uniques avec ce bout de code:
def unique_num(x):
return len(str(x)) == len(set(str(x))
Vous pouvez couper quelques branches si vous êtes à la recherche pour le plus grand nombre. De 6 x 11 = 66 vous savez aussi que l'ampleur du 11 est au plus 5. Une fois que vous connaissez un nombre plus élevé d'une magnitude> = 5 vous pouvez sauter 11.
