Repdigit Base Finding

21

Eine Umstellziffer ist eine natürliche Zahl, die nur durch Wiederholung derselben Ziffer geschrieben werden kann. Zum Beispiel 777ist ein Repdigit, da es sich ausschließlich aus der 7dreimal wiederholten Ziffer zusammensetzt.

Dies ist jedoch nicht nur auf Dezimalzahlen (Basis 10) beschränkt:

  • Jede Mersenne-Zahl (in der Form M n = 2 n -1 ) ist eine Nachkommastelle, wenn sie binär geschrieben ist (Basis 2).
  • Jede Zahl ist eine einfache Umstellung, wenn sie in Unary geschrieben ist (Basis 1).
  • Jede Zahl nkann auch trivial als repdigit 11in base geschrieben werden n-1(z. B. 17wenn hexadezimal geschrieben (base 16) 11, und 3wenn binär geschrieben (base 2), ist dies auch 11).

Hier besteht die Herausforderung darin, andere Basen zu finden, bei denen die eingegebene Nummer eine Umstellziffer sein kann.

Eingang

Eine positive Ganzzahl x > 3in einem beliebigen Format.

Ausgabe

Eine positive Ganzzahl, bbei der (x-1) > b > 1die Darstellung von xin base beine Umstellziffer ist.

  • Ist dies nicht der Fallb , wird eine Ausgabe 0oder ein falscher Wert ausgegeben .
  • Wenn mehrere solcher bvorhanden sind, können Sie einige oder alle ausgeben.

Regeln

  • Die (x-1) > b > 1Einschränkung besteht darin, die unbedeutenden Konvertierungen in unäre oder die "subtrahierende" Basis zu verhindern. Die Ausgabenummer kann in einer unären oder einer beliebigen geeigneten Basis geschrieben werden, aber die Basis selbst darf keine der trivialen Konvertierungen sein.
  • Die Eingabe / Ausgabe kann über jede geeignete Methode erfolgen .
  • Es gelten die üblichen Lückenbeschränkungen.

Beispiele

In --> Out
11 --> 0            (or other falsey value)
23 --> 0            (or other falsey value)
55 --> 10           (since 55 is 55 in base 10)
90 --> 14           (since 90 is 66 in base 14 ... 17, 29, 44 also allowed)
91 --> 9            (since 91 is 111 in base 9 ... 12 also allowed)
AdmBorkBork
quelle
Können wir annehmen, dass die in b ≤ 36vielen Sprachen integrierten Basisumwandlungsfunktionen nicht höher sind?
Türklinke
2
@Doorknob Unter der Annahme , b ≤ 36 stark begrenzt den Umfang dieses Problems, und alle vorhandenen Antworten richtig größere Basen handhaben , so dass ich nicht sagen werde, Sie eine obere auf gebunden nicht davon ausgehen kann , bjenseits dessen, was gegeben wird .
AdmBorkBork
Die meisten Zahlen sind in einer Basis Nachkommastellen. Zum Beispiel ist 91 = 13 * 7, also ist es 77 in der Basis 12.
Neil
@Neil ... Es ist fast so, als wärst du auf etwas ...
AdmBorkBork

Antworten:

11

Jelly, 11 9 Bytes

bRI¬P€TḊṖ

Gibt eine Liste von Basen zurück, die leer (falsch) ist, wenn keine vorhanden ist. Probieren Sie es online!

Wie es funktioniert

bRI¬P€TḊṖ  Main link. Argument: x (number)

 R         Range; yield [1, ..., x].
b          Base; convert x to base n, for each n in the range.
  I        Compute the increment (differences of successive values) of each array
           of base-n digits. This yields only 0's for a repdigit.
   ¬       Apply logical NOT to each increment.
    P€     Compute the product of all lists of increments.
      T    Get the indices of all truthy products.
       Ḋ   Discard the first index (1).
        Ṗ  Discard the last index (x - 1).
Dennis
quelle
9

Pyth, 11 10

fqjQT)r2tQ

Anscheinend sucht Pyths Unary qnach einer Liste, die alle eindeutigen Werte seit ungefähr 10 Tagen enthält. Die Untersuchung von Pyth-Bugs verbessert anscheinend die Golfergebnisse.

Filtert die Liste danach, [2..input-1)ob die eindeutige Ziffernfolge der Eingabe in dieser Basis die Länge 1 hat.

Test Suite

Erläuterung:

r2tQ     ##  generate the python range from 2 to the input (Q) - 1
         ##  python range meaning inclusive lower and exclusive upper bounds
f        ##  filter that list with lambda T:
  jQT    ##  convert the input to base T
 q    )  ##  true if the resulting list digits has all equal elements
FryAmTheEggman
quelle
5

Ruby, 87 69 63 Bytes

->x{(2..x-2).find{|b|y=x;a=y%b;a=0if a!=y%b while(y/=b)>0;a>0}}

Ich musste die Basiskonvertierung von Hand durchführen, da Rubys Buildins nur bis zur Basis 36 reichen ...

Rückgabe nilfür nicht gefunden.

->x{      # anonymous lambda that takes one argument
(2..x-2)  # range of the possible bases to search over
.find{    # return the first element that satisfies the block, or nil if none
|b|       # b represents the base currently being tested
y=x;      # a temporary value to avoid mutating the original value of x
a=y%b;    # the first (well, last) digit in base b, which will be compared to

                   y/=b      # divide the number by the base
   if a!=y%b                 # if this digit does not match (is different)...
a=0                          # set a to a value representing "failure"
             while(    )>0;  # keep doing this until we get zero (no digits left)

a>0       # return whether a has maintained its original value (no digit change)
}}        # find then returns the first element for which this is true (or nil)
Türknauf
quelle
5

Python, 71 72 78 Bytes

lambda x:{b for b in range(2,x-1)for d in range(x)if x*~-b==x%b*~-b**d}

Keine Rekursion, probiert einfach alle Basen aus und gibt eine Reihe von denen aus, die funktionieren.

Es ist verlockend , zu kodieren bund din einer einzigen Zahl, aber es dauert zu viele klammern Ausdrücke sie zu extrahieren. 77 Bytes:

lambda x:{k/x for k in range(2*x,x*x-x))if x*~-(k/x)==x%(k/x)*~-(k/x)**(k%x)}

72 Bytes:

f=lambda x,b=2:b*any(x*~-b==x%b*~-b**d for d in range(x))or f(x,b+1)%~-x

Gibt den ersten aus b , der funktioniert, oder 0falls keiner funktioniert.

Eine Wiederholungseinheit xvon dStellen cin der Basis bhat einen Wertx==c*(b**d-1)/(b-1) . Äquivalent x*(b-1)==c*(b**d-1).

Der Wert cmuss seinx%b die letzte Ziffer sein. Ich sehe jedoch keine Möglichkeit, darithmetisch zu bestimmen , sodass der Code alle Möglichkeiten ausprobiert, um festzustellen , ob einer von ihnen funktioniert.

Gespeichert 5 Bytes durch Kopieren Dennis Tricks des Gebens einer Falsey ausgegeben , wenn berreicht , x-1indem die Ausgabe Modulo unterx-1 . Ein weiteres Byte, das von Dennis gespeichert wurde, erinnert mich daran, dass Exponentiation aus unerklärlichen Gründen eine höhere Priorität hat ~.

Eine gleichlange Lösung mit instatt any.

f=lambda x,b=2:b*(x*~-b in[x%b*~-b**d for d in range(x)])or f(x,b+1)%~-x
xnor
quelle
4

Ruby, 50 Bytes

->n{(2..n-2).find{|b,i=n|i%b==(i/=b)%b ?redo:i<1}}

Ich würde diesen nervigen Raum wirklich gerne entfernen, aber als Neuling in Ruby bin ich mit seinen syntaktischen Macken immer noch nicht vertraut.

xsot
quelle
In diesem Fall ist b?dies ein gültiger Methodenname, sodass Sie den Speicherplatz nicht entfernen können.
Jordan
4

Emojicode , 214 Bytes

(77 Zeichen):

🐇🐹🍇🐇🐖🏁➡🚂🍇🍦b🍺🔲🗞🔷🔡😯🔤🔤🚂🍮i 2🍮n 0🔁◀i➖b 1🍇🍦v🔷🔡🚂b i🍊▶🐔🔫v🔪v 0 1📏v🍇🍮n i🍉🍫i🍉😀🔷🔡🚂n 9🍎0🍉🍉

Gibt die Ergebnisse in Basis 9 aus.

Ich habe vor, seit ein paar Wochen Code-Golf mit Emojicode zu spielen, aber die Sprache ist erst seit kurzem stabil genug, um tatsächlich mit 😉 zu arbeiten. Als Bonus nutzt diese Frage die Funktionalität, die Emojicode eigentlich wirklich gut kann: Ganzzahlen in anderen Basen darstellen.

Ungolfed (👴 ist ein Zeilenkommentar in Emojicode)

🐇🐹🍇         👴 define main class "🐹"
  🐇🐖🏁➡🚂🍇  👴 define main method

    👴 read an integer from stdin, store it in frozen variable "b"
    🍦 b 🍺 🔲 🗞 🔷🔡😯🔤🔤 🚂

    🍮 i 2  👴 i = 2
    🍮 n 0  👴 n = 0

    🔁◀i➖b 1🍇     👴 while i < b - 1
      🍦 v 🔷🔡🚂b i  👴 v = the string representation of b in base i

      👴 Split v on every instance of the first character of v.
      👴 If the length of that list is greater than the actual length of v,
      👴 n = i
      🍊▶🐔🔫v🔪v 0 1📏v🍇
        🍮 n i
      🍉

      🍫 i  👴 increment i
    🍉
    😀 🔷🔡🚂 n 9  👴 represent n in base 9 instead of 10, to save a byte 😜
    🍎 0          👴 return error code 0
  🍉
🍉
Orez
quelle
4

Python 2, 79 Bytes

f=lambda x,b=2:~-b*x in[i%b*~-b**(i/b)for i in range(b*x)]and b or f(x,-~b)%~-x

Probieren Sie es auf Ideone .

Idee

Jedes Wiederholungszeichen x der Basis b> 1 und der Ziffer d <b erfüllt das Folgende.

Bedingung

Da d <b , ist die Abbildung (b, d) ↦ cb + d injektiv.

Da b, x> 1 ist , gilt c <x , also gilt cb + d <cb + b = (c + 1) b ≤ xb .

Dies bedeutet, dass wir , um geeignete Werte für c und d für eine gegebene Basis b zu finden , alle i in [0,…, bx) durchlaufen und prüfen können, ob (b - 1) x == (i% b) (b i / b - 1) .

Code

Das genannte Lambda f testet, ob (b - 1) x in der Menge {(i% b) (b i / b - 1) | 0 ≤ i <bx} , beginnend mit dem Wert b = 2 .

  • Wenn der Test erfolgreich war, geben wir b zurück .

  • Andernfalls rufen wir f erneut auf, wobei das gleiche x und b um 1 erhöht werden .

Da b schließlich x - 1 erreichen kann , nehmen wir das Endergebnis Modulo x - 1 , um in diesem Fall 0 zurückzugeben . Beachten Sie, dass dies nicht passiert, wenn b = 2 die Bedingung erfüllt, da es ohne Rekursion zurückgegeben wird. Die Frage garantiert jedoch, dass in diesem Fall b = 2 <x - 1 ist.

Dennis
quelle
3

Perl 6, 45 43 42 Bytes

{grep 2..$^x-2: {[==] $x.polymod($_ xx*)}}

Erläutert

Als Referenz ist eine Variable $^xin { ... }dasselbe wie doing-> $x { ... }

{grep 2..$^x-2: {[==] $x.polymod($_ xx*)}}
{                                          # Anonymous function taking $x
 grep                                      # Return the all values in
      2..$^x-2: {                          # Range from 2 to $x - 2 satisfying:
                 [==]                      #     Reduce with ==:
                      $x.polymod(          #         (See below for polymod)
                                 $_ xx*    #         An infinite list containing
                                           #         the current value
                                       )}}

Polymod (TL; DR): $n.polymod($b xx *)gibt Ihnen eine umgekehrte Liste von Ziffern / 'Ziffern' für die $nBasis$b

Polymod (Real): Die Polymod-Methode ähnelt fast einer leistungsstärkeren Version der Python- divmodFunktion. $n.polymod(*@args)dividiert $ n durch jeden Wert in * @ args, fügt den Rest ( $n mod $x) zur zurückgegebenen Liste hinzu und verwendet den Quotienten für die nächste Division. Ich habe das Gefühl, dass ich es schlecht erklärt habe. Hier sind einige Beispiele (geschrieben in Perl 6, aber sauber genug, um von den meisten verstanden zu werden, wie ich hoffe):

12.polymod(7)    # returns (5, 1)
# Roughly equivalent to:
(12 mod 7, 12 div 7)

86400.polymod(60,60,24) # returns (0, 0, 0, 1)
# Roughly equivalent to (this will give you an array rather than a list):
my $n = 86400;
my @remainders; # Here lies the end result
for (60, 60, 24) -> $divisor {
    @remainders.push( $n mod $divisor );
    $n div= $divisor;
}
@remainders.push($n)

# This is essentially the base conversion algorithm everyone
# knows and loves rolled into a method.
# Given an infinite list of divisors, polymod keeps going until
# the remainder given is 0.     
0xDEADBEEF.polymod(16 xx *) # returns (15 14 14 11 13 10 14 13)
# Roughly equivalent to (but gives an array rather than a list):
my $n = 0xDEADBEEF;
my @remainders; # Here lies the end result
while $n > 0 {
    @remainders.push( $n mod 16 );
    $n div= 16;
}
Hotkeys
quelle
1
Da Sie " einen oder alle " gültigen Werte ausgeben dürfen , können Sie die grepMethode anstelle der firstMethode verwenden.
Brad Gilbert b2gills
Oh, guter Fang, das habe ich verpasst
Hotkeys
3

Dyalog APL , 28 Bytes

 {b/⍨⍵{1=≢∪⍵⊥⍣¯1⊢⍺}¨b←1+⍳⍵-3}

{... ... }anonyme Funktion angewandt werden , umx (dargestellt durch )
b←1+⍳⍵-3ganze Zahlen von 2 - ⍵-2 gespeichert , wie es b
⍵{... für jedes Element in b ( ), die Funktion anzuwenden {... }mit x als linkem Argumente
⍵⊥⍣¯1⊢⍺convert x auf diese Basis
1=≢∪1 ist gleich die tally der eindeutigen Ziffer?
b/⍨Elemente von b sind wahr (dass es nur eine einzige Ziffer gibt).

Beispielfälle

Wenn keine Basis existiert, ist die Ausgabe leer (was falsch ist), wie durch dieses Programm gezeigt werden kann:

 WhatIsEmpty
 →''/TRUE ⍝ goto (→) TRUE: if (/) emptystring ('')
 'False'
 →END       
TRUE:       
 'True'     
END:        

Dies druckt 'Falsch'

Adam
quelle
2

Pyth, 26 19 Bytes

hMfql{eT1m,djQdr2tQ

Probieren Sie es hier aus!

Ich werde eine Erklärung hinzufügen, nachdem ich das gespielt habe. Schauen Sie sich diese Antwort für eine kürzere Implementierung und Erklärung an.

Denker
quelle
1
Vielen Dank, dass Sie mich daran erinnert haben, dass ich die zusätzlichen Grundlagen für 90und 91in meinen Beispielen vergessen habe!
AdmBorkBork
2

MATL , 15 bis 14 Bytes

3-:Q"G@:YAd~?@

Das funktioniert mit aktuellen Version (14.0.0) der Sprache / des Compilers.

Wenn keine Basis existiert, ist die Ausgabe leer (was falsch ist).

Probieren Sie es online!

3-:Q    % take input x implicitly. Generate range of possible bases: [2,3,...,x-2]
"       % for each base b
  G     %   push input again
  @:    %   generate vector of (1-based) digits in base b: [1,2,...,b]
  YA    %   convert to that base
  d~    %   differences between consecutive digits; negate
  ?     %   if all values are true (that is, if all digits were equal)
    @   %     push that base
        %   end if implicitly
        % end for each implicitly
        % display implicitly
Luis Mendo
quelle
2

Mathematica, 55 Bytes

Cases[4~Range~#-2,a_/;Equal@@#~IntegerDigits~a]/.{}->0&

Anonyme Funktion, nicht zu kompliziert. Filtert einfach die Basen basierend auf der Wiederholbarkeit heraus.

LegionMammal978
quelle
2

Python 2, 75 Bytes

n=input()
b=1
while b<n-2:
 i=n;b+=1
 while i%b==i/b%b:i/=b
 if i<b:print b

Ein Port meiner rubinroten Antwort. Gibt alle gültigen Basen aus, sofern vorhanden.

xsot
quelle
2

Julia, 45 Bytes

n->filter(b->endof(∪(digits(n,b)))<2,2:n-2)

Dies ist eine anonyme Funktion, die eine Ganzzahl akzeptiert und ein Ganzzahl-Array zurückgibt. Um es aufzurufen, weisen Sie es einer Variablen zu. Es werden alle anwendbaren Basen oder ein leeres Array zurückgegeben. Es gibt keine Probleme mit großen Basen.

Zuerst generieren wir den Inklusionsbereich [2, n - 2], wobei n die Eingabe ist. Wir haben dann filterdie Liste nur für ganze Zahlen b, für die n in der Basis b weniger als 2 eindeutige Ziffern hat. Dazu erhalten wir für jede Ganzzahl b im Bereich die Ziffern von n in der Basis b als Array unter Verwendung von digits, erhalten eindeutige Elemente unter Verwendung von und erhalten den Index des letzten Elements (dh die Länge) unter Verwendung vonendof .

Alex A.
quelle
1

Brachylog , 12 Bytes

>>.ℕ₂≜&ḃ↙.=∧

Probieren Sie es online! (als generator!)

Übernimmt die Eingabe über die Eingabevariable und gibt eine Basis über die Ausgabevariable aus, falls dies möglich ist. Andernfalls schlägt dies fehl. Gleichzeitig funktioniert es auch als Generator der eine Liste aller Basen ausgibt, wobei diese Liste leer sein kann.

Im Idealfall könnte dies so aussehen ḃ↙.=&>>, dass möglicherweise die Generatorfunktionalität in dieser oder einer ähnlichen Form geopfert wird (da dies letztendlich unärgerlich werden würde), aber ab sofort sind 12 Byte die kürzesten, die ich weiß, wie ich sie bekomme.

     ≜          Assign an integer value to
  .             the output variable
   ℕ₂           which is greater than or equal to 2
 >              and less than a number
>               which is less than the input.
      &         The input
       ḃ↙.      in base-(the output)
          =     is a repdigit.
           ∧    (which is not necessarily the output)
Nicht verwandte Zeichenfolge
quelle
1

Rubin , 46 43 Bytes

Verwendet die in Ruby 2.4 eingeführte Funktion Integer # digits , um eine manuelle Teilung zu vermeiden.

-3 Bytes dank @Jordan.

->n{(2..n-2).find{|i|!n.digits(i).uniq[1]}}

Probieren Sie es online!

Wert Tinte
quelle
@ Jordan ah ja, ich vergesse immer wieder diesen Trick haha
Value Ink
0

05AB1E , 7 Bytes

ÍL¦ʒвÙg

Gibt alle möglichen Werte oder eine leere Liste als Falsey-Wert aus (obwohl technisch gültige Ausgaben auch Falsey sind, da nur 1 in 05AB1E Wahrheit ist und alles andere Falsey).

Probieren Sie es online aus oder überprüfen Sie alle Testfälle .

Erläuterung:

Í        # Decrease the (implicit) input-integer by 2
 L       # Create a list in the range [1, input-2]
  ¦      # Remove the first value to make the range [2, input-2]
   ʒ     # Filter this list by:
    в    #  Convert the (implicit) input to the base of the number we're filtering
     Ù   #  Uniquify it, leaving only distinct digits
      g  #  Get the length of this, which is truthy (1) if all digits were the same
         # (and then output the filtered list implicitly as result)
Kevin Cruijssen
quelle
0

Perl 5 -Minteger -na , 63 Bytes

map{$r=$,=($c="@F")%$_;$r*=$c%$_==$,while$c/=$_;$r&&say}2..$_-2

Probieren Sie es online!

Gibt alle möglichen Antworten oder nichts aus, wenn keine Lösung vorhanden ist.

Xcali
quelle