Sum the odd square numbers less than N

Question

Write a program or function to output the sum of the odd square numbers (OEIS #A016754) less than an input n.

The first 44 numbers in the sequence are:

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

The formula for the sequence is a(n) = ( 2n + 1 ) ^ 2.

Notes

• Your program's behaviour may be undefined for n < 1 (that is, all valid inputs are >= 1.)

Test cases

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

Answer 1

Jelly, 6 bytes

½Ċ|1c3

Try it online! or verify all test cases.

Background

For all positive integers k, we have 1² + 3² + ⋯ + (2k - 1)² = k(2k - 1)(2k +1) ÷ 3.

Since there are m C r = m! ÷ ((m-r)!r!) r-combinations of a set of m elements, the above can be calculated as (2k + 1) C 3 = (2k + 1)2k(2k - 1) ÷ 6 = k(2k - 1)(2k + 1) ÷ 3.

To apply the formula, we must find the highest 2k + 1 such that (2k - 1)² < n. Ignoring the parity for a moment, we can compute the highest m such that (m - 1)² < n as m = ceil(srqt(n)). To conditionally increment m if it is even, simply compute m | 1 (bitwise OR with 1).

How it works

½Ċ|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).

Answer 2

05AB1E, 10 8 bytes

Code:

<tLDÉÏnO

Explanation:

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

Might come in handy: t;L·<nO.

Uses CP-1252 encoding. Try it online!.

Answer 3

JavaScript (ES6), 30 bytes

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

31 bytes if f(1) needs to return zero instead of false:

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

Answer 4

Haskell, 30 bytes

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

Surprisingly normal-looking.

Answer 5

R, 38 36 bytes

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

@Giuseppe saved two bytes by moving x into the arguments list to save the curly braces. Cool idea!

Ungolfed

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

Try it online!

Answer 6

C#, 126 131 bytes

Edited version to conform with the new question:

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);}}

Using hardcoded limit:

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();}}}

Answer 7

Jelly, 7

’½R²m2S

Try it online or try a modified version for multiple values

Shh... Dennis is sleeping...

Thanks to Sp3000 in chat for their help!

Explanation:

’½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

Answer 8

CJam, 15 Bytes

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

Try it online!

Hardcoded 10000 solutions:

Martin's 12 byte solution:

99,2%:)2f#1b

My original 13 byte solution:

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

Try it online!

Answer 9

Octave, 23 bytes

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

Testing:

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

Answer 10

C, 51, 50 48 bytes

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

Because why not golf in one of the most verbose languages? (Hey, at least it's not Java!)

Try it online!

Full ungolfed program, with test I/O:

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

Answer 11

Actually, 7 bytes

√K1|3@█

Try it online!

Also for 7 bytes:

3,√K1|█

Try it online!

This uses the same formula as in Dennis's Jelly answer.

Explanation:

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

Answer 12

MATL, 10 bytes

qX^:9L)2^s

EDIT (July 30, 2016): the linked code replaces 9L by 1L to adapt to recent changes in the language.

Try it 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

Answer 13

Pyth, 10 bytes

s<#Qm^hyd2

Test suite

Explanation:

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

Answer 14

Mathcad, 31 "bytes"

Note that Mathcad uses keyboard shortcuts to enter several operators, including the definition and all programming operators. For example, ctl-] enters a while loop - it cannot be typed and can only be entered using the keyboard shortcut or from the Programming toolbar. "Bytes" are taken to be the number of keyboard operations needed to enter a Mathcad item (eg, variable name or operator).

As I have no chance of winning this competition, I thought I'd add a bit of variety with a direct formula version.

Answer 15

Racket, 57 bytes

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

Answer 16

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

Based on @Thomas' C# solution.

Explanation:

Try it 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

Answer 17

Python, 42 38 bytes

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

Answer 18

Haskell, 32 31 bytes

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

Usage example: (#1) 9802 -> 166650.

Edit: @xnor saved a byte, with a clever list comprehension. Thanks!

Answer 19

Reng v.3.3, 36 bytes

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

Try it here!

Explanation

1: initialization

 0#ci#m1ø

Sets c to 0 (the counter) and the input I to the max. 1ø goes to the next line.

2: loop

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

: duplicates the current value (the squared odd number) and [I m puts max down. I used the less-than trick in another answer, which I use here. %:1,e checks if the STOS < TOS. If it is, q^ goes up and breaks out of the loop. Otherwise:

         c2*1+²c1+#c

c puts the counter down, 2* doubles it, 1+ adds one, and ² squares it. c1+#C increments c, and the loop goes again.

3: final

        >$a+¡n~

$ drops the last value (greater than desired), a+¡ adds until the stack's length is 1, n~ outputs and terminates.

Answer 20

Python, 39 bytes

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

If, for n=1, it's valid to output False rather than 0, then we can avoid the base case conversion to get 37 bytes

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

It's strange that I haven't found a shorter way to get 0 for i*i>=n and nonzero otherwise. In Python 2, one still gets 39 bytes with

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

Answer 21

PARI/GP, 33 32 26 bytes

Adapted from Dennis' code:

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

My first idea (30 bytes), using a simple polynomial formula:

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

This is an efficient implementation, actually not very different from the ungolfed version I would write:

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

An alternate implementation (37 bytes) which loops over each of the squares:

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

Another alternate solution (35 bytes) demonstrating summing without a temporary variable:

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

Yet another solution, not particularly competitive (40 bytes), using the L² norm. This would be better if there was support for vectors with step-size indices. (One could imagine the syntax n->norml2([1..((n-1)^.5+1)\2..2]) which would drop 8 bytes.)

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

Answer 22

Python 2, 38 bytes

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

Based off Dennis's formula, with s==-2*k. Outputs a float. In effect, the input is square rooted, decremented, then rounded up to the next even number.

Answer 23

Julia, 29 bytes

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

This is a recursive function that accepts an integer and returns an integer.

We start an index at 1 and if its square is less than the input, we take the square and add the result of recusing on the index + 2, which ensures that even numbers are skipped, otherwise we return 0.

Answer 24

Julia, 26 bytes

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

This constructs the range of all odd, positive integers below n and the array of the squares of the integers in that range, then computes the sum of the integers in both iterables.

Try it online!

Answer 25

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;

Answer 26

Clojure, 53 bytes

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

You can check it here: https://ideone.com/WKS4DA

Answer 27

Mathematica 30 bytes

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

This unnamed function squares all odd numbers less than the input (Range[1,Sqrt[#-1],2]) and adds them.

Answer 28

PHP, 64 bytes

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

Expanded:

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

On every iteration of the for loop, it will add 2 to k and check if k² is less than $i, if it is add k² to $a.

Answer 29

R, 60 bytes

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

Does exactly as described in challenge, including returning 0 for the n = 1 case. Degolfed, ';' represents linebreak in R, ignored below:

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

Answer 30

Pyt, 6 bytes

⁻√ř²ƧƩ

Port of FryAmTheEggman's Jelly answer.

Try it online!

Answer 31

dc, 19 bytes

1-v1+2/dd+1+d2-**3/

This uses the closed-form formula ⅓k(2k+1)(2k-1) for the largest k such that (2k-1)² < n

Ungolfed version

As a full program:

#!/usr/bin/dc -f

?                   # input

1-v1+2/             # k
dd+1+d2-            # k, 2k+1, 2k-1
**3/                # multply

p                   # output

Answer 32

Python 3, 61 49 bytes

lambda n:sum(i*i for i in range(1,n,2)if i*i<n)

plenty of savings, thanks for helping me out

Answer 33

Python 2, 49 bytes

This ended up being shorter than a lambda.

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

Try it online

My shortest lambda, 53 bytes:

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

Answer 34

Ruby, 32 bytes

f=->n,i=1{i*i<n ?i*i+f[n,i+2]:0}

Answer 35

Pyke, 7 bytes (noncompetitive)

Add up_to function which repeats until the rtn is above inp.

#}hX)Os

Explanation:

#   )   -  While rtn < input:
        -   i = 0
 }hX    -    rtn = ((i*2)+1)**2
        -   i+=1
     O  -  rtn[:-1]
      s - sum(^)

Try it here!

Answer 36

Factor, 58 57 bytes

[| n | n 2 * iota [ 2 * 1 + 2^ ] map [ n < ] filter sum ]

Well, this was simpler than I thought!

[| n |       ! new local var n
    n 2 *    ! double n
    iota     ! fixnum>range
    [ 
        2 *  ! double 
        1 +  ! + 1
        2^  ! square
    ] map    ! each item in range(0, n*2)
    [ 
        n <  ! entries over n
    ] filter ! keep-only 
    sum ]    ! sum the resulting array

Unit tests, if you like:

{ 0 }  [ 1  sum-odds-lt ] unit-test
{ 1 }  [ 2  sum-odds-lt ] unit-test
{ 1 }  [ 9  sum-odds-lt ] unit-test
{ 10 } [ 10 sum-odds-lt ] unit-test
{ 156849 } [ 9801 sum-odds-lt ] unit-test 
{ 166650 } [ 9802 sum-odds-lt ] unit-test
{ 166650 } [ 10000 sum-odds-lt ] unit-test

Answer 37

bash + bc, 86 bytes

s=0
for((n=0;;n++));{
w=`bc<<<"(2*$n+1)^2"`
[ $w -ge $1 ]&&break;
s=$((s+w))
}
echo $s

This piece of code is quite self explaining, as it simply sums up the values. It is not quite a magic code, as formatting it properly helps... The stop condition is not in the header of the loop, but after evaluating the step and before adding, since here we have all the values we need without initalising them beforehand.

Answer 38

Perl 5, 51 50 bytes

-1 byte thanks to TuukkaX.

Not sure if I can golf this more...

$s=0;map{$_%2?$s+=$_**2:()}(1..(<>-1)**.5);print$s

map checks whether the current value in the array [1.. sqrt(input-1)] is odd or even. If it's odd, increase $s with the odd number squared.