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

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 3

Haskell, 30 bytes

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

Surprisingly normal-looking.

Answer 4

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 5

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 6

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 7

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 8

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 9

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 10

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 11

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 12

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 13

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 14

Racket, 57 bytes

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

Answer 15

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 16

Japt -hx, 6 4 bytes

¬o²ó

Try it

¬o²ó     :Implicit input of integer
¬        :Square root
 o       :Range [0,ceil(¬))
  ²      :Square each
   ó     :Uninterleave
         :Implicit output of sum of last element

Answer 17

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 18

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 19

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 20

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 21

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 22

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 23

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 24

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 25

Clojure, 53 bytes

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

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

Answer 26

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 27

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 28

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 29

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 30

Vyxal sm, 5 bytes

~∷~∆²

Try it Online!

~     # range 1..n-1 (due to m flag) filtered by
 ∷    # is odd
  ~   # filtered by
   ∆² # is a perfect square
      # sum is taken by s flag