Dividende zéro

28

Description du défi

Pour chaque entier positif, nil existe un nombre dont la forme 111...10...000est divisible par, nc'est- à- dire un nombre décimal qui commence par tous 1et se termine par tous 0. Ceci est très facile à prouver: si nous prenons un ensemble de n+1nombres différents sous la forme de 111...111(tous 1), alors au moins deux d'entre eux donneront le même reste après division par n(selon le principe du pigeonhole). La différence de ces deux nombres sera divisible par net aura la forme souhaitée. Votre objectif est d'écrire un programme qui trouve ce numéro.

Description d'entrée

Un entier positif.

Description de la sortie

Un nombre psous la forme de 111...10...000, tel que p ≡ 0 (mod n). Si vous en trouvez plusieurs, affichez-en un (il n'est pas nécessaire que ce soit le plus petit).

Remarques

Votre programme doit donner la réponse dans un délai raisonnable. Ce qui signifie que le forçage brutal n'est pas autorisé:

p = 0
while (p != 11..10.00 and p % n != 0)
    p++

Ce n'est pas non plus:

do
    p = random_int()
while (p != 11..10.00 and p % n != 0)

L'itération à travers les nombres sous forme de 11..10..00est autorisée.

Votre programme n'a pas besoin de gérer une entrée arbitrairement grande - la limite supérieure correspond à la limite supérieure de votre langue.

Exemples de sorties

2: 10
3: 1110
12: 11100
49: 1111111111111111111111111111111111111111110
102: 1111111111111111111111111111111111111111111111110
code-golf math arithmetic number-theory shooqie
la source
Pouvons-nous avoir une limite supérieure raisonnable à la sortie possible? (Quelque chose d'environ moins de 2,4 milliards (environ la valeur maximale d'un entier signé) devrait convenir, car des tableaux ou des listes peuvent être requis pour certaines implémentations)
Tamoghna Chowdhury
@ MartinBüttner Je pense que la première sortie satisfaisante devrait être suffisante (contrainte de délai raisonnable)
Tamoghna Chowdhury
Le dernier 0 n'est pas nécessaire dans le cas de test 49.
CalculatorFeline
@CatsAreFluffy Je pense que tous les nombres doivent contenir au moins 1et au moins un 0, sinon 0c'est une solution pour n'importe quelle entrée. (Ce serait bien de clarifier cela cependant.)
Martin Ender
Exiger juste un 1devrait fonctionner.
CalculatorFeline

Réponses:

22

Mathematica, 29 octets

⌊10^(9EulerPhi@#)/9⌋10^#&

Code de Martin Büttner .

En entrée n, cela renvoie le nombre avec des 9*ϕ(n)uns suivis de nzéros, où ϕest la fonction de totient d'Euler . Avec une fonction phi, cela pourrait être exprimé en Python comme

lambda n:'1'*9*phi(n)+'0'*n

Il suffirait d'utiliser la factorielle à la n!place de ϕ(n), mais en imprimant que beaucoup n'ont pas un temps d'exécution raisonnable.

Affirmation: 9*ϕ(n) ceux suivis de nzéros est un multiple de n.

Preuve: Tout d' abord, prouvent le cas qui nest pas un multiple de 2, 3ou 5. Nous allons montrer que le nombre composé de ϕ(n)uns est un multiple de `n.

Le nombre de kuns est égal à (10^k-1)/9. Puisque nn'est pas un multiple de 3, c'est un multiple de ntant que 10^k-1est un facteur de n, ou de manière équivalente si 10^k = 1 (mod n). Notez que cette formulation fait apparaître que si kfonctionne pour le nombre de uns, il en va de même pour tout multiple de k.

Donc, nous cherchons kà être un multiple de l' ordre de kdans le groupe multiplicatif modulo n . Selon le théorème de Lagrange , un tel ordre est un diviseur de la taille du groupe. Puisque les éléments du groupe sont le nombre de 1à nqui sont relativement premiers à n, sa taille est la fonction de totient d'Euler ϕ(n) . Donc, nous l'avons montré 10^ϕ(n) = 1 (mod n), et donc le nombre composé de ϕ(n)un est un multiple de `n.

Maintenant, traitons les facteurs potentiels de 3in n. Nous savons que 10^ϕ(n)-1c'est un multiple de n, mais (10^ϕ(n)-1)/9peut-être pas. Mais, (10^(9*ϕ(n))-1)/9est un multiple de 9car il est constitué de 9*ϕ(n)uns, donc la somme de ses chiffres est un multiple de 9. Et nous avons noté que la multiplication de l'exposant kpar une constante préserve la divisibilité.

Maintenant, si na des facteurs de 2'et 5', nous devons ajouter des zéros à la fin de la sortie. Il est plus que suffisant d'utiliser des nzéros (en fait, ce log_2(n)serait le cas). Donc, si notre entrée nest divisée en n = 2^a * 5^b * m, il suffit d'en avoir 9*ϕ(m)pour être un multiple de n, multiplié par 10^npour être un multiple de 2^a * 5^b. Et, puisqu'il ns'agit d'un multiple de m, il suffit d'en utiliser 9*ϕ(n). Donc, cela fonctionne pour avoir 9*ϕ(n)ceux suivis de nzéros.

xnor
la source
12
Juste pour m'assurer que personne ne pense que cela a été posté sans ma permission: xnor a proposé la méthode et la preuve tout seul, et je lui ai juste fourni une implémentation Mathematica, car elle a une EulerPhifonction intégrée. Il n'y a rien de stupéfiant à la mise en œuvre réelle, donc je considérerais cela pleinement son propre travail.
Martin Ender
9

Python 2, 44 octets

f=lambda n,j=1:j/9*j*(j/9*j%n<1)or f(n,j*10)

Quand jest une puissance de 10 telle que 1000, la division au sol j/9donne un nombre composé de 1 comme 111. Donc, j/9*jdonne 1 suivi d'un nombre égal de 0 comme 111000.

La fonction teste récursivement les nombres de cette forme, essayant des puissances de plus en plus élevées de 10 jusqu'à ce que nous trouvions celui qui est un multiple du nombre souhaité.

xnor
la source
1
Oh, bon point, il suffit de vérifier 1 ^ n0 ^ n ...
Martin Ender
@ MartinBüttner Si c'est plus simple, il suffit également de fixer le nombre de 0 comme valeur d'entrée. Je ne sais pas s'il est aussi efficace d'imprimer autant de zéros.
xnor
Pourquoi la vérification de 1 ^ n0 ^ n fonctionne-t-elle?
Lynn
5
@Lynn L'ajout de plus de zéros ne peut pas faire de mal, et il y a une infinité de nombres possibles de uns, un certain nombre aura assez de uns et de zéros.
xnor
5

Pyth, 11 octets

.W%HQsjZ`TT

Suite de tests

Fondamentalement, il met simplement un 1 devant et un 0 dans le dos encore et encore jusqu'à ce que le nombre soit divisible par l'entrée.

Explication:

.W%HQsjZ`TT
                Implicit: Q = eval(input()), T = 10
.W              while loop:
  %HQ           while the current value mod Q is not zero
      jZ`T      Join the string "10" with the current value as the separator.
     s          Convert that to an integer.
          T     Starting value 10.
isaacg
la source
4

Haskell, 51 octets

\k->[b|a<-[1..],b<-[div(10^a)9*10^a],b`mod`k<1]!!0

En utilisant l'approche de xnor. nimi a enregistré un octet!

Lynn
la source
3

CJam, 28 25 19 octets

Sauvegardé 6 octets avec l'observation de xnor que nous avons seulement besoin de regarder les numéros du formulaire .1n0n

ri:X,:)Asfe*{iX%!}=

Testez-le ici.

Explication

ri:X    e# Read input, convert to integer, store in X.
,:)     e# Get range [1 ... X].
As      e# Push "10". 
fe*     e# For each N in the range, repeat the characters in "10" that many times,
        e# so we get ["10" "1100" "111000" ...].
{iX%!}= e# Select the first element from the list which is divided by X.
Martin Ender
la source
2

Mathematica, 140 55 octets

NestWhile["1"<>#<>"0"&,"1",FromDigits@#~Mod~x>0&/.x->#]

Beaucoup d'octets supprimés grâce à l'astuce xnor 1 ^ n0 ^ n.

Valeur minimale, 140 156 octets Cela donne la solution la plus petite possible.

NestWhile["1"<>#&,ToString[10^(Length@NestWhileList[If[EvenQ@#,If[10~Mod~#>0,#/2,#/10],#/5]&,#,Divisors@#~ContainsAny~{2, 5}&],FromDigits@#~Mod~m>0&/.m->#]&

Il calcule le nombre de zéros requis, puis vérifie tous les 1décomptes possibles jusqu'à ce que cela fonctionne. Il peut sortir un nombre sans 0 mais cela peut être corrigé en ajoutant un <>"0"droit avant la finale &.

CalculatorFeline
la source
2

Haskell, 37 octets

f n=[d|d<-"10",i<-[1..n*9],gcd n i<2]

Cela utilise le fait que cela fonctionne pour en avoir 9*phi(n), où phiest la fonction de totaux d'Euler. Ici, il est implémenté en utilisant gcdet en filtrant, produisant un chiffre pour chaque valeur iqui est relativement première pour lui qui est dans la plage 1et 9*n. Il suffit également d'utiliser autant de zéros.

xnor
la source
2

JavaScript (ES6), 65 octets

Modifier 2 octets enregistrés thx @Neil

Il fonctionne dans les limites du type numérique javascript, avec 17 chiffres significatifs. (Donc assez limité)

a=>{for(n='';!(m=n+=1)[17];)for(;!(m+=0)[17];)if(!(m%a))return+m}

Moins golfé

function (a) {
    for (n = ''; !(m = n += '1')[17]; )
        for (; !(m += '0')[17]; )
            if (!(m % a))
                 return +m;
}
edc65
la source
1
Pourquoi ne pas for(m=n;?
Neil
@Neil car j'ai besoin d'au moins un zéro. Peut-être que je peux trouver un moyen plus court ... (merci pour l'édition)
edc65
Oh, ce n'était pas clair dans la question, mais je vois maintenant que les sorties d'échantillons ont toutes au moins un zéro. Dans ce cas, vous pouvez toujours enregistrer un octet à l'aide de for(m=n;!m[16];)if(!((m+=0)%a)).
Neil
1
@Neil ou même 2 octets. Thx
edc65
1

Perl 5, 26 octets

comprend un octet pour -n( -M5.01est gratuit)

($.="1$.0")%$_?redo:say$.
msh210
la source
0

bc, 58 octets

define f(n){for(x=1;m=10^x/9*10^x;++x)if(m%n==0)return m;}

Exemples de résultats

200: 111000
201: 111111111111111111111111111111111000000000000000000000000000000000
202: 11110000
203: 111111111111111111111111111111111111111111111111111111111111111111111111111111111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000
204: 111111111111111111111111111111111111111111111111000000000000000000000000000000000000000000000000
205: 1111100000
206: 11111111111111111111111111111111110000000000000000000000000000000000
207: 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
208: 111111000000
209: 111111111111111111000000000000000000
210: 111111000000
211: 111111111111111111111111111111000000000000000000000000000000
212: 11111111111110000000000000
213: 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
214: 1111111111111111111111111111111111111111111111111111100000000000000000000000000000000000000000000000000000
215: 111111111111111111111000000000000000000000
216: 111111111111111111111111111000000000000000000000000000
217: 111111111111111111111111111111000000000000000000000000000000
218: 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
219: 111111111111111111111111000000000000000000000000
Toby Speight
la source
0

dc, 27 octets

Odsm[O*lmdO*sm+O*dln%0<f]sf

Ceci définit une fonction fqui attend son argument dans la variable n. Pour l'utiliser comme programme, ?sn lfx ppour lire depuis stdin, appelez la fonction et imprimez le résultat sur stdout. La variable met le haut de la pile doivent être réinitialisés à 10 (en répétant Odsm) avant de fpouvoir être réutilisés.

Résultats:

200: 111000
201: 111111111111111111111111111111111000000000000000000000000000000000
202: 11110000
203: 111111111111111111111111111111111111111111111111111111111111111111111111111111111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000
204: 111111111111111111111111111111111111111111111111000000000000000000000000000000000000000000000000
205: 1111100000
206: 11111111111111111111111111111111110000000000000000000000000000000000
207: 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
208: 111111000000
209: 111111111111111111000000000000000000
210: 111111000000
211: 111111111111111111111111111111000000000000000000000000000000
212: 11111111111110000000000000
213: 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
214: 1111111111111111111111111111111111111111111111111111100000000000000000000000000000000000000000000000000000
215: 111111111111111111111000000000000000000000
216: 111111111111111111111111111000000000000000000000000000
217: 111111111111111111111111111111000000000000000000000000000000
218: 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
219: 111111111111111111111111000000000000000000000000
Toby Speight
la source