Etant donné un semi-premier N , trouver le plus petit entier positif m tel que la représentation binaire de l'un des deux facteurs de N puisse être trouvée dans la représentation binaire de N * m .

Exemple

Prenons le semi-premier N = 9799 .

Nous essayons différentes valeurs de m , à partir de 1:

 m |  N * m |   N * m in binary
---+--------+------------------
 1 |   9799 |    10011001000111
 2 |  19598 |   100110010001110
 3 |  29397 |   111001011010101
 4 |  39196 |  1001100100011100
 5 |  48995 |  1011111101100011
 6 |  58794 |  1110010110101010
 7 |  68593 | 10000101111110001
 8 |  78392 | 10011001000111000
 9 |  88191 | 10101100001111111
10 |  97990 | 10111111011000110
11 | 107789 | 11010010100001101

Nous nous arrêtons ici parce que contient la représentation binaire du dernier produit 101001qui est la représentation binaire de 41 , l'un des deux facteurs de 9799 (l'autre étant 239 ).

La réponse serait donc 11 .

Règles et notes

• Essayer des valeurs paires de m est inutile. Ils ont été montrés dans l'exemple ci-dessus par souci d'exhaustivité.
• Votre programme doit prendre en charge tout N pour lequel N * m est dans les capacités de calcul de votre langue.
• Vous êtes autorisé à factoriser N avance plutôt que d' essayer chaque sous - chaîne possible de la représentation binaire de N * m pour voir si elle se révèle être un facteur de N .
• Comme l'a prouvé MitchellSpector , m existe toujours.
• Il s'agit de code-golf, donc la réponse la plus courte en octets l'emporte. Les failles standard sont interdites.

Cas de test

La première colonne est l'entrée. La deuxième colonne est la sortie attendue.

         N |    m |         N * m |                              N * m in binary | Factor
-----------+------+---------------+----------------------------------------------+-------
         9 |    3 |            27 |                                      [11]011 |      3
        15 |    1 |            15 |                                       [11]11 |      3
        49 |    5 |           245 |                                   [111]10101 |      7
        91 |    1 |            91 |                                    10[1101]1 |     13
       961 |   17 |         16337 |                             [11111]111010001 |     31
      1829 |    5 |          9145 |                             1000[111011]1001 |     59
      9799 |   11 |        107789 |                          1[101001]0100001101 |     41
     19951 |   41 |        817991 |                       1[1000111]101101000111 |     71
    120797 |   27 |       3261519 |                     11000[1110001]0001001111 |    113
   1720861 |  121 |     208224181 |               11000110100[100111111101]10101 |   2557
 444309323 |  743 |  330121826989 |    100110011011100110010[1101010010101011]01 |  54443
 840000701 | 4515 | 3792603165015 | 11011100110000[1000110000111011]000101010111 |  35899
1468255967 |   55 |   80754078185 |      1001011001101010100010[1110001111]01001 |    911

Pyth, 13 octets

ff}.BY.B*TQPQ

Manifestation

Explication:

ff}.BY.B*TQPQ
f                Find the first integer >= to 1 where the following is true
 f         PQ    Filter the prime factors of the input
        *TQ      Multiply the input by the outer integer
      .B         Convert to a binary string
   .BY           Convert the prime factor to a binary string
  }              Check whether the factor string is in the multiple string.

05AB1E , 18 16 15 octets

-2 octets grâce à Riley!

-1 octet grâce à Emigna!

[N¹*b¹Ñ¦¨båOiNq

Explication:

[                   # Infinite loop start
 N                  # Push the amount of times we have iterated
  ¹*               # Multiplied by input
    b              # Convert to binary
     ¹Ñ¦¨b         # Calculate the proper divisors of the input in binary excluding one
          åO       # Check if a substring of N * m in binary is in the divisors
            iNq    # If so, print how many times we have iterated and terminate the program

Essayez-le en ligne!

JavaScript (ES6), 96 95 80 octets

n=>F=m=>(k=p=>p&&(q=1,g=x=>1<x&&x<n&n%x<1|g(x>>1,q*=2))(p)|k(p-q))(n*m)?m:F(-~m)

Une fonction qui renvoie une fonction récursive qui utilise une fonction récursive qui utilise une fonction récursive. Je commence vraiment à me demander si l' .toString(2)itinéraire serait plus court ...

Attribuer un exemple variable f=n=>...et appel avec une paire supplémentaire de parens, f(9)(). Si ce n'est pas autorisé (la méta publication est à + 6 / -2), vous pouvez utiliser cette version de 83 octets avec invocation standard:

f=(n,m)=>(k=p=>p&&(q=1,g=x=>1<x&&x<n&n%x<1|g(x>>1,q*=2))(p)|k(p-q))(n*m)?m:f(n,-~m)

Les deux versions fonctionnent pour tous sauf les trois derniers cas de test. Vous pouvez également essayer ces cas de test en passant x>>1à (x-x%2)/2.

Utilitaires Bash + Unix, 85 84 octets

for((;;m++)){ dc -e2o$[$1*m]n|egrep -q $(dc "-e2o`factor $1`nBEPn")&&break;}
echo $m

Essayez-le en ligne!

Je soulignerai également que m existe toujours pour tout semi-premier n. Voici pourquoi:

Écrivez n = pq, où p et q sont premiers et p <= q.

Soit b le nombre de chiffres dans la représentation binaire de n-1. Alors, pour tout k compris entre 0 et n-1 inclus, p * (2 ^ b) + k en binaire consiste en la représentation binaire de p suivie de b bits supplémentaires représentant k.

Ainsi, les nombres p * (2 ^ b) + k pour 0 <= k <= n-1, lorsqu'ils sont écrits en binaire, commencent tous par la représentation binaire de p. Mais ce sont n nombres consécutifs, donc l'un d'eux doit être un multiple de n.

Il s'ensuit que nous avons un mn multiple de n dont la représentation binaire commence par la représentation binaire de p.

Sur cette base, on peut trouver une limite supérieure pour m de 2 sqrt (n). (On peut probablement obtenir une limite supérieure beaucoup plus serrée que cela.)

Haskell, 161 octets

import Data.List
(!)=mod
a#b|a!b==0=b|0<1=a#(b+1)
g 0=[]
g n=g(n`div`2)++show(n!2)
(a%b)c|g b`isInfixOf`g(a*c)=c|0<1=a%b$c+1
f n=min(n%(n#2)$1)$n%(n`div`(n#2))$1

Vérification simple. Factorisez d'abord, puis recherchez linéairement en commençant à 1 et prenez le minimum de la valeur pour les deux facteurs.

Prend quelques secondes pour le dernier testcase ( 1468255967), les ghcirapports (15.34 secs, 18,610,214,160 bytes)sur mon ordinateur portable.

Mathematica, 83 octets

1//.x_/;FreeQ[Fold[#+##&]/@Subsequences@IntegerDigits[x#,2],d_/;1<d<#&&d∣#]:>x+1&

Brachylog (2), 14 octets

ḋḃᵐD∧?:.×ḃs∈D∧

Essayez-le en ligne!

Il y a plus d'une façon d'écrire ceci en 14 octets dans Brachylog, donc je suis allé pour le plus efficace. Comme il est courant pour les soumissions Brachylog, il s'agit d'une soumission de fonction; son entrée est le semi-premier, sa sortie est le multiplicateur.

Explication

ḋḃᵐD∧?:.×ḃs∈D∧
ḋ               Prime decomposition (finds the two prime factors)
 ḃᵐ             Convert each factor to binary
   D            Name this value as D
    ∧?          Restart with the user input
      :.×       The output is something that can be multiplied by it
         ḃ      to produce a number which, when expressed in binary
          s     has a substring
           ∈D   that is an element of D
             ∧  (suppress an implicit constraint that D is the output; it isn't)

L'ordre d'évaluation de Prolog et Brachylog est défini par la première contrainte qui ne peut pas être immédiatement déduite de l'entrée. Dans ce programme, c'est une contrainte sur le résultat d'une multiplication, donc l'interpréteur visera à garder les opérandes de la multiplication aussi proches que possible de 0. Nous connaissons l'un des opérandes, et l'autre est la sortie, nous trouvons donc la plus petite sortie possible, ce qui est exactement ce que nous voulons.

PowerShell , 136 octets

param($n)$a=2..($n-1)|?{!($n%$_)}|%{[convert]::ToString($_,2)};for(){$b=[convert]::toString(++$m*$n,2);if($a|?{$b-like"*$_*"}){$m;exit}}

Essayez-le en ligne!

Très long en raison du fonctionnement de la conversion en binaire dans PowerShell. : - /

Prend entrée $n, des boucles à travers 2à $n-1et tire les facteurs !($n%$_). Envoie ceux-ci dans une boucle |%{...}et converts chacun d'eux dans une 2chaîne binaire (de base ). Stocke ces chaînes binaires dans $a.

Ensuite, nous entrons dans une for(){...}boucle infinie . Chaque itération, nous incrémentons ++$m, multiplions celle par $net convertcelle d'une chaîne binaire, stockée dans $b. Ensuite, ifcette chaîne est regex -liketoutes les chaînes $a, nous sortons $met exit.

Perl 6 , 66 octets

->\n{first {(n*$_).base(2)~~/@(grep(n%%*,2..^n)».base(2))/},^∞}

Basé sur des expressions rationnelles.

Super lent, car il force brutalement les facteurs de n à nouveau brutalement à chaque position de correspondance d'expression régulière de chaque nombre qui est essayé.

Le calcul des facteurs une seule fois améliore les performances mais en fait 72 octets:

->\n{my @f=grep(n%%*,2..^n)».base(2);first {(n*$_).base(2)~~/@f/},^∞}