Temuan Basis Repdigit

21

Sebuah repdigit adalah nomor alami yang dapat ditulis sendiri oleh mengulangi angka yang sama. Misalnya, 777adalah repdigit, karena hanya terdiri dari digit yang 7diulang tiga kali.

Ini tidak terbatas pada angka desimal (basis 10) saja, namun:

  • Setiap angka Mersenne (dalam bentuk M n = 2 n -1 ) adalah repdigit ketika ditulis dalam biner (basis 2).
  • Setiap angka sepele adalah repdigit ketika ditulis dalam unary (basis 1).
  • Setiap angka njuga dapat ditulis sepele sebagai repdigit 11dalam basis n-1(misalnya, 17ketika ditulis dalam heksadesimal (basis 16) adalah 11, dan 3ketika ditulis dalam biner (basis 2) juga 11).

Tantangannya di sini adalah menemukan pangkalan - pangkalan lain di mana nomor input mungkin merupakan repdigit.

Memasukkan

Bilangan bulat positif x > 3, dalam format apa pun yang nyaman.

Keluaran

Bilangan bulat positif bdengan di (x-1) > b > 1mana representasi xdalam basis badalah repdigit.

  • Jika tidak bada, output 0atau nilai falsey .
  • Jika ada beberapa b, Anda dapat menampilkan salah satu atau semuanya.

Aturan

  • The (x-1) > b > 1batasan adalah untuk mencegah konversi sepele untuk unary atau "salah satu kurangi" dasar. Nomor output dapat ditulis dalam unary atau basis yang nyaman, tetapi basis itu sendiri tidak boleh menjadi salah satu konversi sepele.
  • Input / output dapat melalui metode yang sesuai .
  • Batasan celah standar berlaku.

Contohnya

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
sumber
Bisakah kita berasumsi b ≤ 36(fungsi konversi basis bawaan banyak bahasa tidak semakin tinggi)?
Gagang pintu
2
@ Doorknob Dengan asumsi b ≤ 36 sangat membatasi ruang lingkup masalah ini, dan semua jawaban yang ada benar menangani basis yang lebih besar, jadi saya akan mengatakan tidak, Anda tidak dapat mengasumsikan batas atas bmelampaui apa yang diberikan.
AdmBorkBork
Sebagian besar angka adalah repdigits di beberapa basis. Misalnya, 91 = 13 * 7 jadi 77 di basis 12.
Neil
@Neil ... Ini hampir seperti Anda sedang melakukan sesuatu, di sana ...
AdmBorkBork

Jawaban:

11

Jelly, 11 9 byte

bRI¬P€TḊṖ

Mengembalikan daftar pangkalan, yang kosong (falsy) jika tidak ada. Cobalah online!

Bagaimana itu bekerja

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
sumber
9

Pyth, 11 10

fqjQT)r2tQ

Rupanya Pyth's unary qmemeriksa daftar yang memiliki semua nilai unik sekitar 10 hari yang lalu. Rupanya menyelidiki bug Pyth meningkatkan skor golf.

Memfilter daftar [2..input-1)jika kumpulan unik dari input pada basis itu adalah panjang 1.

Test Suite

Penjelasan:

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
sumber
5

Ruby, 87 69 63 byte

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

Saya harus menerapkan konversi basis dengan tangan, karena bawaan Ruby hanya naik ke basis 36 ...

Pengembalian nilkarena tidak ditemukan.

->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)
Gagang pintu
sumber
5

Python, 71 72 78 byte

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

Tanpa rekursi, coba saja semua pangkalan dan hasilkan serangkaian yang berfungsi.

Sangat menggoda untuk menyandikan bdan ddalam satu nomor, tetapi terlalu banyak ekspresi yang diurung untuk mengekstraknya. 77 byte:

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 byte:

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

Keluarkan yang pertama bberfungsi, atau 0jika tidak ada yang berhasil.

Sebuah rep unit xdari ddigit cdalam basis bmemiliki nilai x==c*(b**d-1)/(b-1). Setara x*(b-1)==c*(b**d-1),.

Nilainya charus x%b, digit terakhir. Saya tidak melihat cara untuk menentukan secara dhitung, jadi kode mencoba semua kemungkinan untuk melihat apakah ada yang berfungsi.

Disimpan 5 byte dengan menyalin trik Dennis untuk memberikan output falsey ketika bmencapai x-1dengan mengambil modulo output x-1. Byte lain yang disimpan dari Dennis mengingatkan saya bahwa eksponensial tidak dapat dijelaskan memiliki prioritas lebih tinggi dari itu ~.

Solusi dengan panjang yang sama dengan inbukannya 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
Tidak
sumber
4

Ruby, 50 byte

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

Saya benar-benar ingin menghapus ruang yang menjengkelkan itu tetapi sebagai pendatang baru di ruby, saya masih tidak terbiasa dengan kebiasaan sintaksisnya.

xsot
sumber
The quirk menyinggung dalam kasus ini adalah itu b?akan menjadi nama metode yang valid, sehingga Anda tidak dapat menghilangkan ruang.
Jordan
4

Emojicode , 214 byte

(77 karakter):

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

Mencetak hasil dalam basis 9.

Saya bermaksud melakukan golf kode dengan emojicode selama beberapa minggu sekarang, tetapi bahasanya baru-baru ini menjadi cukup stabil untuk benar-benar bekerja dengan 😉. Sebagai bonus, pertanyaan ini memanfaatkan emojicode fungsionalitas yang benar-benar bagus di: mewakili bilangan bulat di basis lain.

Tidak Digubah (👴 adalah komentar baris dalam 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
sumber
4

Python 2, 79 byte

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

Cobalah di Ideone .

Ide

Setiap digit x basis b> 1 dan digit d <b memenuhi yang berikut.

kondisi

Karena d <b , peta (b, d) ↦ cb + d bersifat injeksi.

Juga, karena b, x> 1 , kita memiliki c <x , jadi cb + d <cb + b = (c + 1) b ≤ xb .

Ini berarti bahwa, untuk menemukan nilai yang sesuai untuk c dan d untuk basis b yang diberikan , kita dapat mengulangi semua i di [0, ..., bx) dan memeriksa apakah (b - 1) x == (i% b) (b i / b - 1) .

Kode

Tes lambda f yang bernama apakah (b - 1) x ada di set {(i% b) (b i / b - 1) | 0 ≤ i <bx} , dimulai dengan nilai b = 2 .

  • Jika tes berhasil, kami mengembalikan b .

  • Lain lagi, kita memanggil f lagi, dengan x dan b yang sama bertambah 1 .

Karena b akhirnya dapat mencapai x - 1 , kami mengambil hasil akhir modulo x - 1 untuk mengembalikan 0 dalam kasus ini. Perhatikan bahwa ini tidak akan terjadi jika b = 2 memenuhi syarat, karena dikembalikan tanpa berulang. Namun, pertanyaannya menjamin bahwa b = 2 <x - 1 dalam kasus ini.

Dennis
sumber
3

Perl 6, 45 43 42 byte

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

Dijelaskan (semacam)

Untuk referensi, variabel $^xdalam { ... }sama dengan melakukan-> $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 *)memberi Anda daftar digit / 'digit' terbalik untuk $ndalam basis$b

Polymod (Nyata): Metode polymod hampir seperti versi divmodfungsi python yang lebih kuat . $n.polymod(*@args)Membagi $ n dengan setiap nilai dalam * @ args, menambahkan sisanya ( $n mod $x) ke daftar yang dikembalikan, dan menggunakan hasil bagi untuk divisi berikutnya. Saya merasa saya menjelaskannya dengan buruk jadi inilah beberapa contoh (ditulis dalam perl 6, tetapi cukup bersih untuk dimengerti oleh sebagian besar saya harap):

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;
}
Tombol cepat
sumber
1
Sebenarnya karena Anda diizinkan untuk menampilkan " salah satu atau semua " dari nilai-nilai yang valid, Anda dapat menggunakan grepmetode alih-alih firstmetode.
Brad Gilbert b2gills
Oh tangkapan bagus, saya melewatkan itu
Hotkeys
3

Dyalog APL , 28 byte

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

{... ... }fungsi anonim untuk diterapkan ke x(diwakili oleh )
b←1+⍳⍵-3bilangan bulat dari 2 - ⍵-2 disimpan sebagai b
⍵{... untuk setiap elemen dalam b ( ), terapkan fungsi {... }dengan x sebagai argumen kiri,
⍵⊥⍣¯1⊢⍺konversi x ke basis itu
1=≢∪adalah 1 sama dengan penghitungan digit unik?
b/⍨elemen b di mana benar (bahwa hanya ada satu digit unik).

Contoh kasus

Jika tidak ada basis, output kosong (yang falsey), seperti yang dapat ditunjukkan oleh program ini:

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

Ini mencetak 'Salah'

Adm
sumber
2

Pyth, 26 19 byte

hMfql{eT1m,djQdr2tQ

Coba di sini!

Akan menambahkan penjelasan setelah saya bermain golf ini. Lihatlah jawaban ini untuk implementasi dan penjelasan yang lebih singkat.

Denker
sumber
1
Terima kasih telah mengingatkan saya bahwa saya lupa pangkalan tambahan untuk 90dan 91dalam contoh saya!
AdmBorkBork
2

MATL , 15 14 byte

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

Ini berfungsi dengan versi saat ini (14.0.0) dari bahasa / kompiler.

Jika tidak ada basis, output kosong (yang falsey).

Cobalah 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
sumber
2

Mathematica, 55 byte

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

Fungsi anonim, tidak terlalu rumit. Cukup filter basis berdasarkan repdigit-ness.

LegionMammal978
sumber
2

Python 2, 75 byte

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

Port jawaban ruby ​​saya. Mencetak semua basis yang valid jika ada.

xsot
sumber
2

Julia, 45 byte

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

Ini adalah fungsi anonim yang menerima integer dan mengembalikan array integer. Untuk menyebutnya, tetapkan ke variabel. Ini akan mengembalikan semua basis yang berlaku atau array kosong. Tidak ada masalah dengan pangkalan besar.

Pertama kita menghasilkan rentang inklusif [2, n - 2], di mana n adalah input. Kami kemudian filterdaftar hanya bilangan bulat b yang n di basis b memiliki kurang dari 2 digit unik. Untuk melakukan ini, untuk setiap bilangan bulat b dalam rentang, kita mendapatkan digit n di basis b sebagai array menggunakan digits, mendapatkan item unik menggunakan , dan mendapatkan indeks elemen terakhir (yaitu panjang) menggunakan endof.

Alex A.
sumber
1

Brachylog , 12 byte

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

Cobalah online! (sebagai generator!)

Mengambil input melalui variabel input dan mengeluarkan basis melalui variabel output dalam hal ini mungkin, gagal sebaliknya. Pada saat yang sama, ini juga berfungsi sebagai generator yang menampilkan daftar semua pangkalan, di mana daftar itu bisa kosong.

Idealnya ini bisa terlihat seperti ḃ↙.=&>>, mungkin mengorbankan fungsionalitas generator dalam bentuk itu atau yang serupa (karena akhirnya akan mencapai unary), tetapi sampai sekarang 12 byte adalah yang terpendek yang saya tahu cara mendapatkannya.

     ≜          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)
String yang tidak terkait
sumber
1

Ruby , 46 43 byte

Menggunakan digit # Integer diperkenalkan di Ruby 2.4 untuk menghindari keharusan membagi secara manual.

-3 byte terima kasih kepada @Jordan.

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

Cobalah online!

Nilai Tinta
sumber
@ Jordan ah ya saya selalu lupa trik itu haha
Value Ink
0

05AB1E , 7 byte

ÍL¦ʒвÙg

Keluarkan semua nilai yang mungkin, atau daftar kosong sebagai nilai falsey (walaupun secara teknis output yang valid juga falsey, karena hanya 1 benar di 05AB1E, dan yang lainnya falsey).

Cobalah secara online atau verifikasi semua kasus uji .

Penjelasan:

Í        # 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
sumber
0

Perl 5 -Minteger -na , 63 byte

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

Cobalah online!

Keluarkan semua jawaban yang mungkin atau tidak sama sekali jika tidak ada solusi.

Xcali
sumber