Secuencia de subdivisión de suma

8

Considere los dígitos de cualquier base integral por encima de uno, enumerados en orden. Subdivídalos exactamente por la mitad repetidamente hasta que cada trozo de dígitos tenga una longitud impar:

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

Ahora, para cualquier fila de esta tabla, lea los fragmentos de dígitos subdivididos como números en la base de esa fila y suméelos. Proporcione el resultado en base 10 para mayor comodidad.

Por ejemplo...

  • para la base 3 solo hay un número para sumar: 012 3 = 12 3 = 5 10
  • para la base 4 hay 4 números para sumar: 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

Desafío

Escriba un programa que tome un entero mayor que uno como base y realice este procedimiento de subdivisión de la suma, generando la suma final en la base 10 . (Entonces, si la entrada es 3la salida es 5, si la entrada es 6la salida es 145, etc.)

Escriba una función que tome y devuelva un número entero (o una cadena ya que los números pueden ser bastante grandes) o use stdin / stdout para ingresar y generar los valores.

El código más corto en bytes gana.

Notas

  • Puede usar cualquier función de conversión base incorporada o importada.
  • No hay límite superior para el valor de entrada (además de un valor razonable Int.Max). Los valores de entrada no se detienen en 36 solo porque "Z" se detiene allí .

PD: esta es mi quincuagésima pregunta :)

code-golf math Pasatiempos de Calvin
fuente
si uso una función, ¿qué significa "..la suma final en base 10"? si devolvemos la salida, entonces se representa internamente en la computadora en binario. ¿Qué significa "en base 10" allí?
orgulloso haskeller
2
Felicitaciones por llegar a 50 preguntas. Y una variedad tan asombrosa. Gracias.
DavidC
@proudhaskeller En ese caso, solo dé sus ejemplos en la base 10 si tiene alguno. Aunque también está bien si la función devuelve una cadena ya que los números pueden ser bastante grandes. Luego usa la base 10.
Calvin's Hobbies

Respuestas:

4

CJam, 17 15

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

Funciona si hay una nueva línea final en la entrada.

Una versión más obvia para aquellos que no saben x & -x:

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

Cómo funciona

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
fuente
1
Obtener la mayor potencia de 2 como x & -xes realmente inteligente.
Dennis
Aceptando esto ya que es el más corto, pero apoya a Ell para encontrar una fórmula.
Los pasatiempos de Calvin
11

Pitón, 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))

¿Eh?

  • El número de grupos de dígitos que produce la subdivisión, G , es simplemente la mayor potencia de dos que divide el número de dígitos (es decir, la base), b . Está dado por G = b ^ (b & (b - 1)) , donde ^ es bitwise-XOR. Si estás familiarizado con el hecho de que n es una potencia de dos iff n & (n - 1) = 0, entonces debería ser bastante fácil ver por qué. De lo contrario, resuelva algunos casos (en binario) y quedará claro.

  • El número de dígitos por grupo, g , es simplemente b / G .

  • El primer grupo de dígitos, 012 ... (g-1) , como un número en la base b , es F3.

  • El siguiente grupo, g (g + 1) ... (2g-1) , como un número en la base b , es la suma F4.

  • Más generalmente, el grupo n -ésimo (basado en cero), como un número en la base b , a n , esF5.

  • Recuerde que hay grupos G , por lo tanto, la suma de todos los grupos es F6.1 F6.2
    lo que calcula el programa.

Ana
fuente
Wow, eso es super, ¿cómo descubriste esa fórmula? ¿Te importa si convierto esto a CJam?
Optimizador
@Optimizer ¡Adelante! Escribiré una explicación cuando tenga más tiempo.
Ell
1
+1 si sigues diciendo "¿Eh?" después de leer esa explicación: D
Optimizer
Para ser claros, no porque haya algún error en la explicación, sino porque es demasiado complejo para mi cerebro: D
Optimizer
1
Eso es magico! Puede guardar algunos caracteres utilizando ~: b/G-i-1puede ser b/g+~iy (G-1)*b/2puede ser~-G*b/2
xnor
2

CJam (instantánea), 19 bytes

li__,\mf2m1+:*/fb:+

Tenga en cuenta que la última versión estable (0.6.2) tiene un error que puede hacer mfque se devuelvan enteros en lugar de largos. Paradójicamente, esto se puede eludir al convertir a entero ( :i).

Para ejecutar esto con CJam 0.6.2 (por ejemplo, con el intérprete en línea ), debe usar el siguiente código:

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

Alternativamente, puede descargar y construir la última instantánea ejecutando los siguientes comandos:

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

Casos de prueba

$ 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

Cómo funciona

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

Haskell, 74 69 55

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

ejemplos:

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

CJam, 41 bytes

Esta es básicamente la solución de Ell en CJam:

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

Pruébalo en línea aquí

Mi presentación original:

No funciona correctamente para la base 11 y superior

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

Intentaré ver si puedo hacer que funcione para la base 11 y superior, sin aumentar mucho el tamaño.

Optimizador
fuente
1

Mathematica, 114 bytes (o 72 bytes)

Hm, esto se hizo más largo de lo que pensaba:

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

Y sin golfos:

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

Alternativamente, si solo porto la ingeniosa fórmula de Ell, son 72 bytes:

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

J - 22 char

Función que toma un solo argumento (llámelo ypara los propósitos de este golf) a la derecha

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

Primero usamos 1&q:para obtener el número de veces que yes divisible por 2, y luego dividimos -ypor 2 tantas veces. Esto nos da el negativo del ancho en el que necesitamos dividir las cosas, lo cual es perfecto, porque ]\tomará piezas superpuestas si el argumento es positivo, y no se superpondrá si es negativo.

Entonces dividimos i.y—los enteros de 0 y-1a— en vectores de estos anchos, y los usamos #.para convertirlos de base ya base 10. Finalmente, +/sumamos y terminamos.

Ejemplos: (la entrada en J REPL está sangrada, la salida queda al ras)

   +/@(#.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
Algoritmo de tiburón
fuente
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++}}

o

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}

La segunda función es similar a la de Ell. El primero utiliza un enfoque más tradicional. Ambos tienen 89 caracteres de tamaño.

Pruebe aquí: http://jsfiddle.net/wndv1zz8/1/

mi gato y yo
fuente
0

Jalea , 10 9 bytes

Ḷœs&N$ðḅS

Pruébalo en línea!

Esencialmente solo una traducción de la respuesta CJam de jimmy23013, excepto el uso n & -ndirecto como el número de fragmentos para dividir.

        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.

(El ðno tiene nada que ver con el mapeo: ḅsimplemente vectoriza sobre su argumento izquierdo, y ðestá ahí para separarse ḅScomo una nueva cadena diádica que toma el resultado ḶœsÇcomo argumento izquierdo y el argumento del enlace principal como argumento derecho).

Cadena no relacionada
fuente