Subdivide-Sum Sequence

8

Pertimbangkan digit setiap basis integral di atas yang tercantum dalam urutan. Membagi mereka tepat menjadi dua berulang-ulang sampai setiap potongan digit memiliki panjang ganjil:

Base    Digits              Subdivided Digit Chunks
2       01                  0 1
3       012                 012
4       0123                0 1 2 3
5       01234               01234
6       012345              012 345
7       0123456             0123456
8       01234567            0 1 2 3 4 5 6 7
9       012345678           012345678
10      0123456789          01234 56789
11      0123456789A         0123456789A
12      0123456789AB        012 345 678 9AB
...                                                        
16      0123456789ABCDEF    0 1 2 3 4 5 6 7 8 9 A B C D E F
...

Sekarang, untuk setiap baris dalam tabel ini, baca potongan digit yang dibagi sebagai angka di dasar baris itu, dan jumlahkan. Berikan hasilnya di base 10 untuk kenyamanan.

Sebagai contoh...

  • untuk base 3 hanya ada satu nomor untuk dijumlahkan: 012 3 = 12 3 = 5 10
  • untuk base 4 ada 4 angka untuk dijumlahkan: 0 4 + 1 4 + 2 4 + 3 4 = 12 4 = 6 10
  • base 6: 012 6 + 345 6 = 401 6 = 145 10
  • base 11: 0123456789A 11 = 2853116705 10

Tantangan

Tulis program yang menggunakan bilangan bulat lebih besar dari satu sebagai basis dan melakukan prosedur pembagian jumlah ini, mengeluarkan jumlah akhir dalam basis 10 . (Jadi jika input adalah 3output 5, jika input adalah 6output 145, dll.)

Entah menulis fungsi yang mengambil dan mengembalikan integer (atau string karena jumlahnya bisa cukup besar) atau menggunakan stdin / stdout untuk memasukkan dan menampilkan nilai.

Kode terpendek dalam byte menang.

Catatan

  • Anda dapat menggunakan fungsi konversi basis bawaan atau yang diimpor.
  • Tidak ada batas atas nilai input (selain masuk akal Int.Max). Nilai input tidak berhenti di 36 hanya karena "Z" berhenti di sana .

ps ini pertanyaan saya yang kelima puluh :)

code-golf math Hobi Calvin
sumber
jika saya menggunakan fungsi, apa artinya ".. jumlah akhir dalam basis 10" artinya? jika kita mengembalikan output, maka itu direpresentasikan secara internal di komputer dalam biner. apa yang dimaksud "dalam basis 10" di sana?
haskeller bangga
2
Selamat telah mencapai 50 pertanyaan. Dan varietas yang menakjubkan. Terima kasih.
DavidC
@proudhaskeller Dalam kasus itu, berikan saja contoh Anda di basis 10 jika Anda punya. Meskipun itu juga baik-baik saja jika fungsi mengembalikan sebuah string karena jumlahnya bisa cukup besar. Kemudian gunakan basis 10.
Hobbies Calvin

Jawaban:

4

CJam, 17 15

q5*~W*&/\,/fb:+

Bekerja jika ada baris tambahan di input.

Versi yang lebih jelas bagi mereka yang tidak tahu x & -x:

q5*~(~&/\,/fb:+

Bagaimana itu bekerja

q5*~               " Push 5 times the input as numbers. ";
W*&/               " Calculate n / (n & -n). (Or n / (n & ~(n-1))) ";
\,                 " List the digits. ";
/                  " Split into chunks. ";
fb:+               " Sum in the correct base. ";
jimmy23013
sumber
1
Mendapatkan kekuatan tertinggi 2 karena x & -xsangat pintar.
Dennis
Menerima ini karena ini adalah yang terpendek, tetapi mendukung Ell untuk menemukan formula.
Calvin Hobbies
11

Python, 82 78

def f(b):G=b^b&b-1;return sum(b**(b/G-i-1)*(G*i+(G-1)*b/2)for i in range(b/G))

Hah?

  • Jumlah kelompok digit yang dihasilkan oleh subdivison, G , hanyalah kekuatan terbesar dari dua yang membagi jumlah digit (yaitu basis), b . Ini diberikan oleh G = b ^ (b & (b - 1)) , di mana ^ adalah bitwise-XOR. Jika Anda terbiasa dengan fakta bahwa n adalah kekuatan dua iff n & (n - 1) = 0 maka itu harus cukup mudah untuk melihat alasannya. Jika tidak, selesaikan beberapa kasus (dalam biner) dan itu akan menjadi jelas.

  • Jumlah digit per kelompok, g , hanya b / G .

  • Grup digit pertama, 012 ... (g-1) , sebagai angka dalam basis b , adalah F3.

  • Grup berikutnya, g (g + 1) ... (2g-1) , sebagai angka dalam basis b , adalah jumlah F4.

  • Lebih umum, n kelompok -th (zero-based), sebagai nomor dalam basis b , a n , adalah F5.

  • Ingatlah bahwa ada kelompok G , maka jumlah semua kelompok adalah F6.1 F6.2
    yang dihitung oleh program.

Elo
sumber
Wow, itu super, bagaimana Anda mengetahui formula itu? Keberatan jika saya mengonversikan ini menjadi CJam?
Pengoptimal
@Optimizer Silakan! Saya akan menulis penjelasan ketika saya punya waktu lagi.
Ell
1
+1 jika Anda masih suka "Hah?" setelah membaca penjelasan itu: D
Optimizer
Hanya untuk menjadi jelas, bukan karena ada kesalahan dalam penjelasan, tetapi karena terlalu rumit untuk otak saya: D
Optimizer
1
Itu ajaib! Anda dapat menyimpan beberapa karakter dengan menggunakan ~: b/G-i-1bisa b/g+~idan (G-1)*b/2bisa~-G*b/2
xnor
2

CJam (snapshot), 19 byte

li__,\mf2m1+:*/fb:+

Perhatikan bahwa rilis stabil terbaru (0.6.2) memiliki bug yang dapat menyebabkan mfmengembalikan bilangan bulat bukan Longs. Cukup paradoks, ini dapat dielakkan dengan casting ke integer ( :i).

Untuk menjalankan ini dengan CJam 0.6.2 (mis., Dengan penerjemah online ), Anda harus menggunakan kode berikut:

li__,\mf:i2m1+:*/fb:+

Atau, Anda dapat mengunduh dan membuat snapshot terbaru dengan menjalankan perintah berikut:

hg clone http://hg.code.sf.net/p/cjam/code cjam-code
cd cjam-code/
ant

Uji kasus

$ cjam <(echo 'li__,\mf2m1+:*/fb:+') <<< 3; echo
5
$ cjam <(echo 'li__,\mf2m1+:*/fb:+') <<< 4; echo
6
$ cjam <(echo 'li__,\mf2m1+:*/fb:+') <<< 6; echo
145
$ cjam <(echo 'li__,\mf2m1+:*/fb:+') <<< 11; echo
2853116705

Bagaimana itu bekerja

li                     " N := int(input()) ";
   _,                  " A := [ 0 1 ... (N - 1) ] ";
  _  \mf               " F := factorize(N) ";
        2m1+           " F := F - [2] + [1] ";
            :*         " L := product(F) ";
              /        " A := A.split(L) ";
               fb      " A := { base(I, N) : I ∊ A } ";
                 :+    " R := sum(A) ";
Dennis
sumber
2

Haskell, 74 69 55

f n=sum[(n-x)*n^mod(x-1)(until odd(`div`2)n)|x<-[1..n]]

contoh:

*Main> map f [2..15]
[1,5,6,194,145,22875,28,6053444,58023,2853116705,2882,2103299351334,58008613,2234152501943159]
haskeller bangga
sumber
1

CJam, 41 byte

Ini pada dasarnya adalah solusi Ell di CJam:

ri:B__(^2/):G/,{_BBG/@-(#G@*G(B2/*+*}/]:+

Cobalah online di sini

Kiriman asli saya:

Tidak berfungsi dengan benar untuk basis 11 ke atas

ri:B2%BB{2/_2%!}g?B,s/:i:+AbBb

Akan mencoba untuk melihat apakah saya bisa membuatnya bekerja untuk basis 11 dan di atas, tanpa menambah ukuran.

Pengoptimal
sumber
1

Mathematica, 114 byte (atau 72 byte)

Hm, ini lebih lama dari yang saya kira:

f@b_:=Tr[#~FromDigits~b&/@({Range@b-1}//.{a___,x_List,c___}/;EvenQ[l=Length@x]:>Join@@{{a},Partition[x,l/2],{c}})]

Dan ungolfed:

f@b_ := Tr[#~FromDigits~
     b & /@ ({Range@b - 1} //. {a___, x_List, c___} /; 
       EvenQ[l = Length@x] :> Join @@ {{a}, Partition[x, l/2], {c}})]

Atau, jika saya hanya mem-porting rumus bagus Ell, itu 72 byte:

f=Sum[#^(#/g-i-1)(g*i+(g-1)#/2),{i,0,#/(g=Floor[BitXor[#,#-1]/2+1])-1}]&
Martin Ender
sumber
1

J - 22 char

Berfungsi mengambil argumen tunggal (sebut saja yuntuk keperluan golf ini) di sebelah kanan.

+/@(#.i.]\~-%2^0{1&q:)

Pertama kita gunakan 1&q:untuk mendapatkan jumlah berapa kali ydibagi 2, dan kemudian bagi -y2 sebanyak itu. Ini memberi kita negatif dari lebar yang kita perlu untuk membagi hal-hal menjadi, yang sempurna, karena ]\akan mengambil potongan tumpang tindih jika argumennya positif, dan non-tumpang tindih jika itu negatif.

Jadi kemudian kita berpisah i.y— bilangan bulat dari 0 ke — y-1menjadi vektor dengan lebar ini, dan gunakan #.untuk mengubahnya dari basis yke basis 10. Akhirnya, +/lakukan penjumlahan, dan kita selesai.

Contoh: (input pada J REPL diindentasi, output rata rata)

   +/@(#.i.]\~-%2^0{1&q:) 6
145
   f =: +/@(#.i.]\~-%2^0{1&q:)
   f 11
2853116705
   (,: f every) 1+i.14   NB. make a little table for 1 to 14
1 2 3 4   5   6     7  8       9    10         11   12            13       14
0 1 5 6 194 145 22875 28 6053444 58023 2853116705 2882 2103299351334 58008613
   f every 20 30 40x     NB. x for extended precision
5088086 7455971889417360285373 368128332
   ":"0 f every 60 240 360 480 720 960x   NB. ":"0 essentially means "align left"
717771619660116058603849466
3802413838066881388759839358554647144
37922443403157662566333312695986004014731504774215618040741346803890772359370271801118861585493594866582351161148652
256956662280637244030391695293099315292368
2855150453577666748223324970642938808770913717928692581430408703547858603387919699948659399838672549766810262282841452256553202264
17093564446058417577302441219081667908764017056
algoritme hiu
sumber
0

JavaScript, 99 89 byte

function f(n){m=n/(n&-n);for(r=s=i=0;;){if(!(i%m)){r+=s;s=0;if(i==n)return r;}s=s*n+i++}}

atau

function g(n){c=n&-n;for(s=i=0;i<n/c;++i)s+=Math.pow(n,n/c-i-1)*(c*i+(c-1)*n/2);return s}

Fungsi kedua mirip dengan fungsi Ell. Yang pertama menggunakan pendekatan yang lebih tradisional. Keduanya berukuran 89 karakter.

Coba di sini: http://jsfiddle.net/wndv1zz8/1/

saya dan kucing saya
sumber
0

Jelly , 10 9 byte

Ḷœs&N$ðḅS

Cobalah online!

Pada dasarnya hanya terjemahan jawaban CJam jimmy23013, kecuali menggunakan n & -nlangsung sebagai jumlah potongan untuk dipecah menjadi.

        S    The sum of
Ḷ            the range from 0 to the input minus one
 œs          split into sublists of length equal to
   &         the input bitwise AND
    N$       its negation
      ðḅ     with each sublist converted from base-the-link's-argument.

(Tidak ðada hubungannya dengan pemetaan: ḅhanya vektorisasi atas argumen kirinya, dan ðada untuk memisahkan ḅSsebagai rantai diad baru yang mengambil hasil ḶœsÇsebagai argumen kiri dan argumen ke tautan utama sebagai argumen kanannya.)

String yang tidak terkait
sumber