Escrever um programa ou função para saída a soma de números quadrados ímpares (OEIS # A016754) menos de uma entrada n .

Os primeiros 44 números da sequência são:

1, 9, 25, 49, 81, 121, 169, 225, 289, 361, 441, 529, 625, 729, 841, 961, 1089, 
1225, 1369, 1521, 1681, 1849, 2025, 2209, 2401, 2601, 2809, 3025, 3249, 3481, 
3721, 3969, 4225, 4489, 4761, 5041, 5329, 5625, 5929, 6241, 6561, 6889, 7225, 7569

A fórmula para a sequência é a(n) = ( 2n + 1 ) ^ 2.

Notas

• O comportamento do seu programa pode ser indefinido n < 1(ou seja, todas as entradas válidas são >= 1).

Casos de teste

1 => 0
2 => 1
9 => 1
10 => 10
9801 => 156849
9802 => 166650
10000 => 166650

Gelatina, 6 bytes

½Ċ|1c3

Experimente online! ou verifique todos os casos de teste .

fundo

Para todos os números inteiros positivos k , temos 1² + 3² + ⋯ + (2k - 1) ² = k (2k - 1) (2k +1) ÷ 3 .

Como existem m C r = m! ÷ ((mr)! R!) R - combinações de um conjunto de m elementos, o acima pode ser calculado como (2k + 1) C 3 = (2k + 1) 2k (2k - 1) ÷ 6 = k (2k - 1) (2k + 1) ÷ 3.

Para aplicar a fórmula, devemos encontrar os 2k + 1 mais altos, de modo que (2k - 1) ² <n . Ignorando a paridade por um momento, podemos calcular o m mais alto, de modo que (m - 1) ² <n como m = ceil (srqt (n)) . Para incrementar condicionalmente m, se for par, simplesmente calcule m | 1 (OR bit a bit com 1 ).

Como funciona

½Ċ|1c3  Main link. Argument: n

½       Compute the square root of n.
 Ċ      Round it up to the nearest integer.
  |1    Bitwise OR with 1 to get an odd number.
    c3  Compute (2k + 1) C 3 (combinations).

JavaScript (ES6), 30 bytes

f=(n,i=1)=>n>i*i&&i*i+f(n,i+2)

31 bytes se f(1)precisar retornar zero em vez de falso:

f=(n,i=1)=>n>i*i?i*i+f(n,i+2):0

05AB1E , 10 8 bytes

Código:

<tLDÉÏnO

Explicação:

<         # Decrease by 1, giving a non-inclusive range.
 t        # Take the square root of the implicit input.
  L       # Generate a list from [1 ... sqrt(input - 1)].
   DÉÏ    # Keep the uneven integers of the list.
      n   # Square them all.
       O  # Take the sum of the list and print implicitly.

Pode vir a calhar: t;L·<nO.

Usa a codificação CP-1252 . Experimente online! .

Haskell, 30 bytes

f n=sum[x^2|x<-[1,3..n],x^2<n]

Surpreendentemente normal.

C #, 126 131 bytes

Versão editada para estar de acordo com a nova pergunta:

class P{static void Main(){int x,s=0,n=int.Parse(System.Console.ReadLine());for(x=1;x*x<n;x+=2)s+=x*x;System.Console.Write(s);}}

Usando limite codificado:

using System;namespace F{class P{static void Main(){int x,s=0;for(x=1;x<100;x+=2)s+=x*x;Console.Write(s);Console.Read();}}}

Gelatina, 7

’½R²m2S

Experimente online ou tente uma versão modificada para vários valores

Shh ... Dennis está dormindo ...

Obrigado ao Sp3000 no chat por sua ajuda!

Explicação:

’½R²m2S
’           ##  Decrement to prevent off-by-one errors
 ½R²        ##  Square root, then floor and make a 1-indexed range, then square each value
    m2      ##  Take every other value, starting with the first
      S     ##  sum the result

R, 38 36 bytes

function(n,x=(2*0:n+1)^2)sum(x[x<n])

O @ Giuseppe salvou dois bytes movendo x- se para a lista de argumentos para salvar os chavetas. Idéia legal!

Ungolfed

function(n, x = (2*(0:n) + 1)^2)  # enough odd squares (actually too many)
  sum(x[x < n])                   # subset on those small enough
}

Experimente online!

C, 51, 50 48 bytes

f(n,s,i)int*s;{for(*s=0,i=1;i*i<n;i+=2)*s+=i*i;}

Porque por que não jogar golfe em uma das línguas mais detalhadas? (Ei, pelo menos não é Java!)

Experimente online!

Programa completo, com E / S de teste:

int main()
{
    int s;
    f(10, &s);
    printf("%d\n", s);
    char *foobar[1];
    gets(foobar);
}

f(n,s,i)int*s;{for(*s=0,i=1;i*i<n;i+=2)*s+=i*i;}

Na verdade, 7 bytes

√K1|3@█

Experimente online!

Também para 7 bytes:

3,√K1|█

Experimente online!

Isso usa a mesma fórmula da resposta de Dennis's Jelly.

Explicação:

√K1|3@█
√K       push ceil(sqrt(n))
  1|     bitwise-OR with 1
    3@█  x C 3

Oitava, 23 bytes

@(x)(x=1:2:(x-1)^.5)*x'

Teste:

[f(1); f(2); f(3); f(10); f(9801); f(9802); f(10000)]
ans =    
        0
        1
        1
       10
   156849
   166650
   166650

CJam, 15 bytes

qi(mq,2%:)2f#1b

Experimente online!

Soluções 10000 codificadas:

Solução de 12 bytes de Martin:

99,2%:)2f#1b

Minha solução original de 13 bytes:

50,{2*)2#}%:+

Experimente online!

Pitão, 10 bytes

s<#Qm^hyd2

Suíte de teste

Explicação:

s<#Qm^hyd2
    m          Map over the range of input (0 ... input - 1)
       yd      Double the number
      h        Add 1
     ^   2     Square it
 <#            Filter the resulting list on being less than
   Q           The input
s              Add up what's left

Mathcad, 31 "bytes"

Observe que o Mathcad usa atalhos de teclado para inserir vários operadores, incluindo a definição e todos os operadores de programação. Por exemplo, ctl-] insere um loop while - ele não pode ser digitado e só pode ser digitado usando o atalho de teclado ou na barra de ferramentas Programação. "Bytes" são considerados o número de operações do teclado necessárias para inserir um item do Mathcad (por exemplo, nome da variável ou operador).

Como não tenho chance de vencer essa competição, pensei em acrescentar um pouco de variedade à versão direta da fórmula.

Raquete, 57 bytes

(λ(n)(for/sum([m(map sqr(range 1 n 2))]#:when(< m n))m))

MATL , 10 bytes

qX^:9L)2^s

EDIT (30 de julho de 2016): o código vinculado substitui 9Lpor 1Lpara se adaptar às alterações recentes no idioma.

Experimente online!

q    % Implicit input. Subtract 1
X^   % Square root
:    % Inclusive range from 1 to that
9L)  % Keep odd-indexed values only
2^   % Square
s    % Sum of array

Python, 39 bytes

f=lambda n,i=1:+(i*i<n)and i*i+f(n,i+2)

Se, por n=1, é válido produzir em Falsevez de 0, podemos evitar a conversão de caso base para obter 37 bytes

f=lambda n,i=1:i*i<n and i*i+f(n,i+2)

É estranho que eu não tenha encontrado um caminho mais curto para chegar 0por i*i>=ne diferente de zero caso contrário. No Python 2, ainda se obtém 39 bytes com

f=lambda n,i=1:~-n/i/i and i*i+f(n,i+2)

Python, 42 38 bytes

f=lambda n,i=1:i*i<n and i*i+f(n,i+2)

Python 2, 38 bytes

s=(1-input()**.5)//2*2;print(s-s**3)/6

Baseado na fórmula de Dennis , com s==-2*k. Produz um flutuador. Com efeito, a entrada é quadrada, decrementada e arredondada para o próximo número par.

PARI / GP , 33 32 26 bytes

Adaptado do código de Dennis :

n->t=(1-n^.5)\2*2;(t-t^3)/6

Minha primeira ideia (30 bytes), usando uma fórmula polinomial simples:

n->t=((n-1)^.5+1)\2;(4*t^3-t)/3

Esta é uma implementação eficiente, na verdade não muito diferente da versão não destruída que eu escreveria:

a(n)=
{
  my(t=ceil(sqrtint(n-1)/2));
  t*(4*t^2-1)/3;
}

Uma implementação alternativa (37 bytes) que faz um loop sobre cada um dos quadrados:

n->s=0;t=1;while(t^2<n,s+=t^2;t+=2);s

Outra solução alternativa (35 bytes) demonstrando a soma sem uma variável temporária:

n->sum(k=1,((n-1)^.5+1)\2,(2*k-1)^2)

Outra solução, não particularmente competitiva (40 bytes), usando a norma L ² . Isso seria melhor se houvesse suporte para vetores com índices de tamanho de etapa. (Pode-se imaginar a sintaxe n->norml2([1..((n-1)^.5+1)\2..2])que diminuiria 8 bytes.)

n->norml2(vector(((n-1)^.5+1)\2,k,2*k-1))

Haskell, 32 31 bytes

 n#x=sum[x^2+n#(x+2)|x^2<n]
 (#1)

Exemplo de uso: (#1) 9802-> 166650.

Edit: @xnor salvou um byte, com uma compreensão inteligente da lista. Obrigado!

Julia, 29 bytes

f(n,i=1)=i^2<n?i^2+f(n,i+2):0

Esta é uma função recursiva que aceita um número inteiro e retorna um número inteiro.

Começamos um índice em 1 e, se seu quadrado for menor que a entrada, pegamos o quadrado e adicionamos o resultado de recusar o índice + 2, o que garante que os números pares sejam ignorados, caso contrário, retornamos 0.

Oracle SQL 11.2, 97 bytes

SELECT NVL(SUM(v),0)FROM(SELECT POWER((LEVEL-1)*2+1,2)v FROM DUAL CONNECT BY LEVEL<:1)WHERE v<:1;

Julia, 26 bytes

x->sum((r=1:2:x-1)∩r.^2)

Isso constrói o intervalo de todos os números inteiros positivos ímpares abaixo de n e a matriz dos quadrados dos números inteiros nesse intervalo e calcula a soma dos números inteiros nos dois iteráveis.

Experimente online!

Reng v.3.3, 36 bytes

0#ci#m1ø>$a+¡n~
:m%:1,eq^c2*1+²c1+#c

Experimente aqui!

Explicação

1: inicialização

 0#ci#m1ø

Define cpara 0(o contador) e a entrada Ipara o mmachado. 1øvai para a próxima linha.

2: loop

:m%:1,eq^c2*1+²c1+#c

:duplica o valor atual (o número ímpar ao quadrado) e [I mcoloca o mmachado para baixo. Usei o truque menos do que em outra resposta , que uso aqui. %:1,everifica se o STOS <TOS. Se for, q^sobe e interrompe o ciclo. De outra forma:

         c2*1+²c1+#c

ccoloca o balcão no chão, 2*dobra, 1+adiciona um e o coloca ao ²quadrado. c1+#Cincrementa ce o loop continua novamente.

3: final

        >$a+¡n~

$descarta o último valor (maior que o desejado), a+¡adiciona até que o comprimento da pilha seja 1, n~sai e termina.

Clojure, 53 bytes

#(reduce +(map(fn[x](* x x))(range 1(Math/sqrt %)2)))

Você pode conferir aqui:  https://ideone.com/WKS4DA

Mathematica 30 bytes

Total[Range[1,Sqrt[#-1],2]^2]&

Esta função sem nome esquadrinha todos os números ímpares menos que a entrada ( Range[1,Sqrt[#-1],2]) e os adiciona.

PHP, 64 bytes

function f($i){$a=0;for($k=-1;($k+=2)*$k<$i;$a+=$k*$k);echo $a;}

Expandido:

function f($i){
    $a=0;
    for($k=-1; ($k+=2)*$k<$i; $a+=$k*$k);
    echo $a;
}

Em cada iteração do forloop, ele irá adicionar 2 a k e verifique se k ² é menor que $i, se for add k ² para $a.

R, 60 bytes

function(n){i=s=0;while((2*i+1)^2<n){s=s+(2*i+1)^2;i=i+1};s}

Faz exatamente como descrito no desafio, incluindo retornar 0 para o caso n = 1. Degolfado, ';' representa quebra de linha em R, ignorado abaixo:

function(n){         # Take input n
i = s = 0            # Declare integer and sum variables
while((2*i+1)^2 < n) # While the odd square is less than n
s = s + (2*i+1)^2    # Increase sum by odd square
i = i + 1            # Increase i by 1
s}                   # Return sum, end function expression

Java 8, 128 119 117 111 49 bytes

n->{int s=0,i=1;for(;i*i<n;i+=2)s+=i*i;return s;}

Baseado na solução C # da @Thomas .

Explicação:

Experimente online.

n->{           // Method with integer as both parameter and return-type
  int s=0,     //  Sum, starting at 0
      i=1;     //  Index-integer, starting at 1
  for(;i*i<n;  //  Loop as long as the square of `i` is smaller than the input
      i+=2)    //    After every iteration, increase `i` by 2
    s+=i*i;    //   Increase the sum by the square of `i`
  return s;}   //  Return the result-sum

Python 2, 49 bytes

Isso acabou sendo mais curto que um lambda.

x=input()
i=1;k=0
while i*i<x:k+=i*i;i+=2
print k

Experimente online

Meu menor lambda, 53 bytes :

lambda x:sum((n-~n)**2for n in range(x)if(n-~n)**2<x)