Semua palindromic dasar Anda adalah milik kami

20

Hasilkan nomorn urut basis dengan palindrome ( OEIS A126071 ).

Secara khusus, urutan didefinisikan sebagai berikut: diberi nomor n, ungkapkan dalam basis auntuk a = 1,2, ..., n, dan hitung berapa banyak dari ekspresi itu yang palindromik. "Palindromic" dipahami dalam hal membalikkan adigit basis ekspresi sebagai unit atom (terima kasih, @Martin Büttner ). Sebagai contoh, pertimbangkan n= 5:

  • a=1: ekspresinya adalah 11111: palindromic
  • a=2: ekspresinya adalah 101: palindromic
  • a=3: ekspresinya adalah 12: tidak palindromik
  • a=4: ekspresinya adalah 11: palindromic
  • a=5: ekspresinya adalah 10: tidak palindromik

Karena itu hasilnya n=5adalah 3. Perhatikan bahwa OEIS menggunakan basis 2, ..., n+1alih-alih 1, ..., n(terima kasih, @beaker ). Ini setara, karena ekspresi dalam basis 1dan n+1selalu palindromik.

Nilai pertama dari urutan tersebut adalah

 1, 1, 2, 2, 3, 2, 3, 3, 3, 4, 2, 3, 3, 3, 4, 4, 4, 4, 2, 4, 5, ...

Input adalah bilangan bulat positif n. Output adalah nsyarat pertama dari urutan.

Program ini secara teoritis harus bekerja (diberikan cukup waktu dan memori) untuk setiap nbatasan yang disebabkan oleh tipe data default Anda dalam setiap perhitungan internal.

Semua fungsi diizinkan. Jumlah byte terendah menang.

Luis Mendo
sumber
Terkait
Luis Mendo
1
Jika ini bermanfaat bagi siapa pun, perlu dicatat bahwa bilangan n juga selalu palindromic pada basis n-1.
Computronium
Ini A126071
Titus

Jawaban:

9

Pyth, 13 byte

mlf_ITjLdSdSQ

ISingkatnya ini sebagian besar disebabkan oleh perintah " Invarian" yang tidak dapat dinilai.

msf_ITjLdSdSQ       implicit: Q=input
m         d         map lambda d over
           SQ       Inclusive range 1 to Q
      jLdSd         Convert d to all the bases between 1 and d
  f                  filter lambda T:
   _IT                 is invariant under reverse
 l                  number that are invariant under reverse

Jika Truemerupakan keluaran yang dapat diterima untuk 1, msm_IjdkSdSQ(12 byte) berfungsi.

Coba di sini .

lirtosiast
sumber
2
Lihat saran FryAmTheEggman untuk menggunakan _I#daripada f_IT(Saya tidak 100% yakin itu tersedia, tetapi tampaknya sudah ).
Jonathan Allan
7

Jelly, 14 byte

bR‘$µ=UP€S
RÇ€

Cobalah online!

Versi yang tidak bersaing

Juru bahasa Jelly memiliki bug yang membuat mengonversi ke unary menjadi tidak mungkin. Ini telah diperbaiki sekarang, jadi kode berikut ( 12 byte ) juga menyelesaikan tugas yang ada.

bRµ=UP€S
RÇ€

Cobalah online!

Bagaimana itu bekerja

bR‘$µ=UP€S  Helper link. Argument: z

 R‘$        Apply range and increment, i.e., map z to [2, ..., z + 1].
            In the non-competing version R simply maps z to [1, ... z].
b           Convert z to each of the bases to the right.
    µ       Begin a new, monadic chain. Argument: base conversions
     =U     Compare the digits of each base with the reversed digits.
            = has depth 0, so [1,2,3]=[1,3,3] yields [1,0,1].
       P€   Take the product of the innermost arrays.
         S  Sum all resulting Booleans.


RÇ€         Main link. Argument: n

R           Yield [1, ..., n].
 ǀ         Apply the helper link to each.
Dennis
sumber
4

MATL , 19 20 byte

:"0@XK:Q"K@:YAtP=A+

Menggunakan rilis saat ini (10.1.0) , yang lebih awal dari tantangan ini.

Cobalah online !

Penjelasan

:            % vector [1,2,...,N], where "N" is implicit input
"            % for each number in that vector
  0          % push 0
  @          % push number 1,2,...N corresponding to current iteration, say "n" 
  XK         % copy n to clipboard
  :Q         % vector [2,3,...,n+1]
  "          % for each number "m" in that vector
    K        % push n
    @:       % vector [1,2,...,m]
    YA       % express n in base m with symbols 1,2,...,m
    tP       % duplicate and permute
    =A       % 1 if all entries are equal (palindrome), 0 otherwise
    +        % add that number
             % implicitly close the two loops and display stack contents
Luis Mendo
sumber
2

CJam, 20 byte

ri{)_,f{)b_W%=}1bp}/

Uji di sini.

Martin Ender
sumber
1

Haskell, 88 byte

a!b|a<b=[a]|1>0=mod a b:(div a b)!b
f n=[1+sum[1|x<-[2..y],y!x==reverse(y!x)]|y<-[1..n]]
Damien
sumber
1

ES6, 149 byte

n=>[...Array(n)].map((_,i)=>[...Array(i)].reduce((c,_,j)=>c+(''+(a=q(i+1,j+2,[]))==''+a.reverse()),1),q=(n,b,d)=>n<b?[n,...d]:q(n/b|0,b,[n%b,...d]))

Bekerja untuk pangkalan> 36 juga.

Neil
sumber
1

JavaScript (ES6), 105 95 byte

f=(n,b)=>b?b<2?1:f(n,b-1)+([...s=n.toString(b)].reverse().join``==s):n<2?[1]:[...f(n-1),f(n,n)]

Penjelasan

Mengambil angka dari 1 hingga 36 (batasan konversi basis dalam JavaScript) dan mengembalikan array urutannya.

Fungsi rekursif yang memeriksa palindrom ketika basis dilewatkan, jika tidak maka akan mengembalikan urutan jika ndilewati saja.

f=(n,b)=>

  // Base palindrome checking
  b?
    b<3?1:                 // return 1 for base-1, since toString(2)
    f(n,b-1)+(             // return the sum of all lower bases and check  this
      [...s=n.toString(b)] // s = n in base b
      .reverse().join``==s // add 1 if it is a palindrome
    )

  // Sequence generation
  :
    n<2?[1]:               // return 1 for the first value of the sequence
    [...f(n-1),f(n,n)]     // return the value for n after the previous values

Uji

var solution = f=(n,b)=>b?b<2?1:f(n,b-1)+([...s=n.toString(b)].reverse().join``==s):n<2?[1]:[...f(n-1),f(n,n)]
<input type="number" oninput="result.textContent=solution(+this.value)" />
<pre id="result"></pre>

pengguna81655
sumber
Apakah ada cara untuk mengubahnya menjadi fungsi rekursif? Saya merasa seperti itu bisa menghemat beberapa byte.
Mama Fun Roll
@ ՊՓԼՃՐՊՃՈԲՍԼ Kamu benar. Terima kasih atas tipnya.
user81655
1

PHP, 73 +1 byte

while(++$i<$argn)$c+=strrev($n=base_convert($argn,10,$i+1))==$n;echo$c+1;

bekerja untuk pangkalan 1untuk 36. Jalankan sebagai pipa dengan -nRatau coba online .

Titus
sumber
1

PHP, 92 +1 byte:

for($b=$c=1;$b++<$n=$argn;$c+=$a==array_reverse($a))for($a=[];~~$n;$n/=$b)$a[]=$n%$b;echo$c;

bekerja untuk semua pangkalan. Jalankan sebagai pipa dengan -nRatau coba online .

Titus
sumber
1

Python 2, 97 byte

c=1;n=int(input())
for b in range(2,n):
	a=[];z=n
	while z:a+=[z%b];z//=b
	c+=a[::-1]==a
print c

Posting Python pertama saya, sebenarnya kode Python pertama saya sama sekali
mungkin memiliki beberapa potensi golf.

Cobalah online!

Titus
sumber
1

> <>, 197 + 2 Bytes

+2 untuk -v flag

:1+0v    ;n\
1\  \$:@2(?/
:<~$/?)}:{:*}}@:{{
\   \~0${:}
>$:@1(?\::4[:&r&r]:$&@@&%:&@&$@-$,5[1+{]$~{{:@}}$@,$
~~1 \  \
?\~0>$:@2(?\$1-:@3+[}]4[}1-]=
 \  /@@r/!?/
r@+1/)0:<
  /?/$-1$~<
~$/       \-1

tio.run tampaknya tidak mengembalikan output apa pun untuk n> 1, tetapi Anda dapat memverifikasinya di https://fishlanguage.com . Masukan masuk ke kotak "Tumpukan awal".

Sasha
sumber
1

Japt , 10 byte

õ_õ!ìZ èêS

Cobalah


Penjelasan

õ              :Range [1,input]
 _             :Map each Z
  õ            :  Range [1,Z] (let's call each X)
   !ìZ         :   Convert Z to a base X digit array
       è       :  Count
        êS     :   Palindromes
Shaggy
sumber
1
õ_õ hahaha nice emoji
Luis felipe De jesus Munoz
1

Python 2 , 85 byte

def f(a):b,c=2,0;exec'd,m=[],a\nwhile m:d+=[m%b];m/=b\nc+=d[::-1]==d;b+=1;'*a;print c

Cobalah online!

Mengharapkan integer sebagai argumen.

Penjelasan:

# named function
def f(a):
    # initialize variable to track base (b) and to track palindromes (c)
    b,c=2,0
        # construct code
        '
        # initialize variable to store remainders (m) and to track divisor (d)
        m,d=[],a
        # while d is not zero,
        # add the current remainder to the array
        # and divide d by the base and assign the result back to d
        while d:m+=[m%b];d/=b
        # False == 0 and True == 1, so add 1 to total if m == reversed(m)
        c+=m[::-1]==m;
        # increment base
        # terminate with ; so that next statement can be executed separately
        b+=1;
        '
    # execute constructed statement (a) times
    exec'....................................................'*a
    # print result
    print c
Triggernometri
sumber