Subdivide-Sum-Sequenz

8

Betrachten Sie die Ziffern einer Integralbasis über einer, die in der angegebenen Reihenfolge aufgeführt sind. Teilen Sie sie wiederholt genau in zwei Hälften, bis jeder Ziffernblock eine ungerade Länge hat:

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
...

Lesen Sie nun für jede Zeile in dieser Tabelle die unterteilten Ziffernblöcke als Zahlen in der Basis dieser Zeile und summieren Sie sie. Geben Sie das Ergebnis der Einfachheit halber in Basis 10 an.

Zum Beispiel...

  • Für Basis 3 gibt es nur eine zu summierende Zahl: 012 3 = 12 3 = 5 10
  • Für Basis 4 gibt es 4 Zahlen zu summieren: 0 4 + 1 4 + 2 4 + 3 4 = 12 4 = 6 10
  • Basis 6: 012 6 + 345 6 = 401 6 = 145 10
  • Basis 11: 0123456789A 11 = 2853116705 10

Herausforderung

Schreiben Sie ein Programm, das eine ganze Zahl größer als eins als Basis verwendet und diese Unterteilungssummenprozedur ausführt, wobei die endgültige Summe in Basis 10 ausgegeben wird . (Wenn also der Eingang 3der Ausgang ist 5, wenn der Eingang 6der Ausgang ist 145, usw.)

Schreiben Sie entweder eine Funktion, die eine Ganzzahl (oder eine Zeichenfolge, da die Zahlen ziemlich groß werden können) annimmt und zurückgibt, oder verwenden Sie stdin / stdout, um die Werte einzugeben und auszugeben.

Der kürzeste Code in Bytes gewinnt.

Anmerkungen

  • Sie können alle integrierten oder importierten Basiskonvertierungsfunktionen verwenden.
  • Es gibt keine Obergrenze für den Eingabewert (außer einer vernünftigen Int.Max). Die Eingabewerte hören nicht bei 36 auf, nur weil "Z" dort stoppt .

ps das ist meine fünfzigste frage :)

code-golf math Calvins Hobbys
quelle
Wenn ich eine Funktion verwende, welche Bedeutung bedeutet "..die endgültige Summe in Basis 10"? Wenn wir die Ausgabe zurückgeben, wird sie intern im Computer binär dargestellt. Was bedeutet "in Basis 10" dort?
stolzer Haskeller
2
Herzlichen Glückwunsch zum Erreichen von 50 Fragen. Und so eine erstaunliche Vielfalt. Vielen Dank.
DavidC
@proudhaskeller In diesem Fall geben Sie einfach Ihre Beispiele in Basis 10 an, falls Sie welche haben. Es ist jedoch auch in Ordnung, wenn die Funktion eine Zeichenfolge zurückgibt, da die Zahlen sehr groß sein können. Dann verwendet Basis 10.
Calvins Hobbys

Antworten:

4

CJam, 17 15

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

Funktioniert, wenn die Eingabe einen nachgestellten Zeilenumbruch enthält.

Eine offensichtlichere Version für diejenigen, die nicht wissen x & -x:

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

Wie es funktioniert

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
quelle
1
Die höchste Potenz von 2 zu bekommen, x & -xist wirklich klug.
Dennis
Dies zu akzeptieren , da es ist die kürzeste, aber Requisiten Ell für eine Formel zu finden.
Calvins Hobbys
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))

Huh?

  • Die Anzahl der Zifferngruppen, die die Unterteilung ergibt, G , ist einfach die größte Zweierpotenz, die die Anzahl der Ziffern (dh die Basis) teilt, b . Es ist gegeben durch G = b ^ (b & (b - 1)) , wobei ^ bitweise XOR ist. Wenn Sie mit der Tatsache vertraut sind, dass n eine Zweierpotenz ist, wenn n & (n - 1) = 0 ist, sollte es ziemlich einfach sein zu verstehen, warum. Andernfalls arbeiten Sie einige Fälle aus (binär) und es wird klar.

  • Die Anzahl der Stellen pro Gruppe, g , ist einfach B / G .

  • Die erste Zifferngruppe 012 ... (g-1) als Zahl in Basis b ist F3.

  • Die nächste Gruppe, g (g + 1) ... (2g-1) , als Zahl in Basis b , ist die Summe F4.

  • Allgemeiner gesagt , die n - ten Gruppe (Null-Basis) als Zahl zur Basis b , a n ist F5.

  • Denken Sie daran, dass es G- Gruppen gibt, daher F6.1 F6.2
    berechnet das Programm die Summe aller Gruppen .

Ell
quelle
Wow, das ist super, wie hast du diese Formel herausgefunden? Stört es Sie, wenn ich dies in CJam konvertiere?
Optimierer
@Optimizer Mach weiter! Ich werde eine Erklärung schreiben, wenn ich noch etwas Zeit habe.
Ell
1
+1 wenn du immer noch wie "Huh?" nach dem Lesen dieser Erklärung: D
Optimizer
Nur um klar zu sein, nicht weil es einen Fehler in der Erklärung gibt, sondern weil es zu komplex für mein Gehirn ist: D
Optimizer
1
Das ist Magie! Sie können einige Zeichen speichern, indem Sie verwenden ~: b/G-i-1kann sein b/g+~iund (G-1)*b/2kann sein~-G*b/2
xnor
2

CJam (Schnappschuss), 19 Bytes

li__,\mf2m1+:*/fb:+

Beachten Sie, dass die neueste stabile Version (0.6.2) einen Fehler aufweist , der dazu führen kann, dass mfGanzzahlen anstelle von Longs zurückgegeben werden. Paradoxerweise kann dies umgangen werden, indem in integer ( :i) umgewandelt wird.

Um dies mit CJam 0.6.2 (z. B. mit dem Online-Interpreter ) auszuführen , müssen Sie den folgenden Code verwenden:

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

Alternativ können Sie den neuesten Snapshot herunterladen und erstellen, indem Sie die folgenden Befehle ausführen:

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

Testfälle

$ 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

Wie es funktioniert

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
quelle
2

Haskell, 74 69 55

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

Beispiele:

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

CJam, 41 Bytes

Dies ist im Grunde Ell's Lösung in CJam:

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

Probieren Sie es hier online aus

Mein ursprünglicher Beitrag:

Funktioniert nicht richtig für Base 11 und höher

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

Ich werde versuchen zu sehen, ob ich es für Base 11 und höher zum Laufen bringen kann, ohne die Größe stark zu erhöhen.

Optimierer
quelle
1

Mathematica, 114 Bytes (oder 72 Bytes)

Hm, das wurde länger als ich dachte:

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

Und ungolfed:

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

Wenn ich nur Ell's raffinierte Formel portiere, sind es alternativ 72 Bytes:

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

J - 22 char

Funktion mit einem einzigen Argument (nennen Sie es yfür die Zwecke dieses Golfs) auf der rechten Seite.

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

Zuerst verwenden wir, um 1&q:zu ermitteln, wie oft ydurch 2 teilbar ist, und dann so oft durch 2 zu teilen -y. Dies gibt uns das Negative der Breite, in die wir die Dinge aufteilen müssen, was perfekt ist, weil]\ überlappende Teile benötigt werden, wenn das Argument positiv ist, und nicht überlappend, wenn es negativ ist.

Dann teilen wir die i.yganzen Zahlen von 0 bis y-1in Vektoren dieser Breiten auf und #.konvertieren sie von Basis yzu Basis 10. Schließlich+/ wird die Summierung durchgeführt, und wir sind fertig.

Beispiele: (Eingabe an der J REPL ist eingerückt, Ausgabe ist linksbündig)

   +/@(#.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
Algorithmushai
quelle
0

JavaScript, 99 89 Bytes

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++}}

oder

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}

Die zweite Funktion ähnelt der von Ell. Der erste verwendet einen traditionelleren Ansatz. Beide sind 89 Zeichen groß.

Versuchen Sie es hier: http://jsfiddle.net/wndv1zz8/1/

ich und meine Katze
quelle
0

Gelee , 10 9 Bytes

Ḷœs&N$ðḅS

Probieren Sie es online aus!

Im Wesentlichen nur eine Übersetzung der CJam-Antwort von jimmy23013, außer dass sie n & -ndirekt als Anzahl der zu teilenden Chunks verwendet wird.

        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.

(Das ðhat nichts mit Mapping zu tun: Es ḅvektorisiert nur über sein linkes Argument und ðdient dazu, ḅSsich als neue dyadische Kette abzutrennen, die das Ergebnis ḶœsÇals linkes Argument und das Argument zum Hauptlink als rechtes Argument verwendet.)

Nicht verwandte Zeichenfolge
quelle