Sequência de soma de subdivisões

8

Considere os dígitos de qualquer base integral acima de uma, listados em ordem. Subdividi-los exatamente ao meio repetidamente até que cada pedaço de dígitos tenha um comprimento ímpar:

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

Agora, para qualquer linha nesta tabela, leia os blocos de dígitos subdivididos como números na base dessa linha e some-os. Dê o resultado na base 10 por conveniência.

Por exemplo...

  • para a base 3, existe apenas um número para somar: 012 3 = 12 3 = 5 10
  • para a base 4, existem 4 números para somar: 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

Desafio

Escreva um programa que utilize um número inteiro maior que um como base e execute esse procedimento de soma subdividida, produzindo a soma final na base 10 . (Portanto, se a entrada é 3a saída 5, se a entrada é 6a saída 145, etc.)

Escreva uma função que pegue e retorne um número inteiro (ou string, pois os números podem ficar muito grandes) ou use stdin / stdout para inserir e gerar valores.

O código mais curto em bytes vence.

Notas

  • Você pode usar qualquer função de conversão básica incorporada ou importada.
  • Não há limite superior para o valor de entrada (além de um razoável Int.Max). Os valores de entrada não param em 36 apenas porque "Z" para aí .

ps esta é a minha quinquagésima pergunta :)

code-golf math Passatempos de Calvin
fonte
se eu usar uma função, o que significa "..a soma final na base 10" significa? se retornarmos a saída, ela será representada internamente no computador em binário. o que significa "na base 10" lá?
proud haskeller
2
Parabéns por alcançar 50 perguntas. E uma variedade tão surpreendente. Obrigado.
DavidC 28/09
@proudhaskeller Nesse caso, apenas dê seus exemplos na base 10, se você tiver algum. Embora também esteja tudo bem se a função retornar uma string, pois os números podem ser bem grandes. Então usa a base 10.
Calvin's Hobbies

Respostas:

4

CJam, 17 15

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

Funciona se houver uma nova linha à direita na entrada.

Uma versão mais óbvia para quem não sabe x & -x:

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

Como 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
fonte
1
Conseguir a potência mais alta de 2, como x & -xé realmente inteligente.
Dennis
Aceitar isso, já que é o mais curto, mas ajuda Ell a encontrar uma fórmula.
Passatempos de Calvin
11

Pitão, 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))

Hã?

  • O número de grupos de dígitos que a subdivisão gera, G , é simplesmente a maior potência de dois que divide o número de dígitos (ou seja, a base), b . É dado por G = b ^ (b & (b - 1)) , onde ^ é bit a bit-XOR. Se você está familiarizado com o fato de que n é uma potência de dois iff n & (n - 1) = 0 , deve ser bem fácil entender o porquê. Caso contrário, elabore alguns casos (em binário) e isso ficará claro.

  • O número de dígitos por grupo, g , é simplesmente b / L .

  • O primeiro grupo de dígitos, 012 ... (g-1) , como um número na base b , é F3.

  • O próximo grupo, g (g + 1) ... (2g-1) , como um número na base b , é a soma F4.

  • De maneira mais geral, o n- ésimo grupo (com base em zero), como um número na base b , a n , é F5.

  • Lembre-se de que existem grupos G , portanto, a soma de todos os grupos é o F6.1 F6.2
    que o programa calcula.

Ell
fonte
Uau, isso é super, como você descobriu essa fórmula? Se importa se eu converter isso para CJam?
Optimizer
@Optimizer Vá em frente! Vou escrever uma explicação quando tiver mais tempo.
Ell
1
+1 se você ainda gosta de "Hein?" depois de ler essa explicação: D
Optimizer
Só para ficar claro, não porque haja qualquer falha na explicação, mas porque o seu complexo demais para meu cérebro: D
Optimizer
1
Isso é mágico! Você pode salvar alguns caracteres usando ~: b/G-i-1pode b/g+~ie (G-1)*b/2pode ser~-G*b/2
xnor
2

CJam (instantâneo), 19 bytes

li__,\mf2m1+:*/fb:+

Observe que a versão estável mais recente (0.6.2) possui um bug que pode causar o mfretorno de números inteiros em vez de longos. Paradoxalmente, isso pode ser contornado ao converter para inteiro ( :i).

Para executar isso com o CJam 0.6.2 (por exemplo, com o intérprete online ), você deve usar o seguinte código:

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

Como alternativa, você pode fazer o download e criar a captura instantânea mais recente executando os seguintes comandos:

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

Casos de teste

$ 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

Como 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
fonte
2

Haskell, 74 69 55

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

exemplos:

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

CJam, 41 bytes

Esta é basicamente a solução de Ell no CJam:

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

Experimente online aqui

Minha submissão original:

Não funciona corretamente para a base 11 e superior

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

Tentarei ver se consigo fazê-lo funcionar na base 11 e acima, sem aumentar muito o tamanho.

Optimizer
fonte
1

Mathematica, 114 bytes (ou 72 bytes)

Hm, isso ficou mais longo do que eu pensava:

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

E não destruído:

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

Como alternativa, se eu apenas portar a fórmula bacana de Ell, serão 72 bytes:

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

J - 22 char

Função com um único argumento (chame-o ypara os fins deste golfe) à direita.

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

Primeiro, usamos 1&q:para obter o número de vezes que yé divisível por 2 e, em seguida, dividimos -ypor 2 tantas vezes. Isso nos dá o negativo da largura em que precisamos dividir as coisas, o que é perfeito, porque ]\terá partes sobrepostas se o argumento for positivo e não sobrepostas se for negativo.

Então, dividimos i.y- os números inteiros de 0 a y-1- em vetores dessas larguras e usamos #.para convertê-los da base ypara a base 10. Finalmente, +/faz a soma e terminamos.

Exemplos: (a entrada no J REPL é recuada, a saída fica nivelada à esquerda)

   +/@(#.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
algoritmshark
fonte
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++}}

ou

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}

A segunda função é semelhante à de Ell. O primeiro usa uma abordagem mais tradicional. Ambos têm 89 caracteres.

Tente aqui: http://jsfiddle.net/wndv1zz8/1/

eu e meu gato
fonte
0

Geléia , 10 9 bytes

Ḷœs&N$ðḅS

Experimente online!

Essencialmente, apenas uma tradução da resposta CJam de jimmy23013, exceto usando n & -ndiretamente como o número de pedaços 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.

( ðIsso não tem nada a ver com mapeamento: ḅapenas vetoriza sobre seu argumento esquerdo e ðexiste para se separar ḅScomo uma nova cadeia diádica que leva o resultado ḶœsÇcomo argumento esquerdo e o argumento para o link principal como argumento correto.)

String não relacionada
fonte