# Sum the odd square numbers less than N

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

• Neither of the close reasons on this are valid reasons to close a challenge... – user45941 Apr 24 '16 at 5:29

# Jelly, 6 bytes

½Ċ|1c3


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


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


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

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


Surprisingly normal-looking.

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

• Welcome to Programming Puzzles and Code Golf! The agreed-upon format for answer headers here is # Language name, number bytes for consistency. – cat Apr 21 '16 at 11:56
• Why do you Console.Read at the end? – Martin Ender Apr 21 '16 at 11:57
• namespaces aren't required for single files. – ASCII-only Apr 21 '16 at 12:01
• You also should be able to save a few bytes by doing System.Console.Write(s); if it works, and if you don't need theConsole.Read. – ASCII-only Apr 21 '16 at 12:04
• @Thomas You can run your program with Ctrl+F5 in VS in which case the window will remain open after the program terminates. – Martin Ender Apr 21 '16 at 12:22

# 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

• Dennis is actually awake. – Dennis Apr 21 '16 at 13:52
• @Dennis Ahh! And alert too, apparently... – FryAmTheEggman Apr 21 '16 at 13:53
• – mbomb007 Apr 21 '16 at 14:31

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

• Welcome to PPCG! – Martin Ender Feb 16 '18 at 16:24
• This site is awesome, thanks! – Michael M Feb 16 '18 at 16:51
• You should be able to save two bytes by moving x into a default function argument and then you can remove the braces. – Giuseppe Feb 17 '18 at 2:17

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

• most verbose languages More golfy than Python, C#, LISP, Forth, etc, C is actually pretty good for golf – cat Apr 22 '16 at 0:59
• @cat I don't think it's more golfy than python. It's definitely better than java, rust and C#, but every python answer on this challenge is < 50 bytes. Also, there's a relevant meta post here. – James Apr 22 '16 at 1:03

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

• Will the next one be called Literally? – cat Apr 25 '16 at 20:14

# 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


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

• Your code is 14 bytes (you had a trailing linefeed in the link), but I think it's not correct for input 9801, since the challenge asks for the squares smaller than the input. – Martin Ender Apr 21 '16 at 12:45
• @MartinButtner Yes, you're right. I'll see if I can find an elegant fix – A Simmons Apr 21 '16 at 14:00

# 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
^   2     Square it
<#            Filter the resulting list on being less than
Q           The input

• Alternative (10 byte): s<#Q%2t^R2 – Leaky Nun Apr 22 '16 at 15:31

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.

• How is MathCAD scored? Where can I get it? – cat Apr 22 '16 at 1:01
• The explanation of scoring you give is kinda... flimsy, IMO – cat Apr 22 '16 at 1:02
• You need to make a meta question for the scoring of this language. – user45941 Apr 22 '16 at 4:10
• Meta question sounds good. Trying to give a non-flimsy explantion for the scoring would rapidly turn into War and Peace. – Stuart Bruff Apr 22 '16 at 9:01

# Racket, 57 bytes

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


# 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


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

• bool is a subclass of int in Python, which means False is an acceptable value for 0. – cat Apr 22 '16 at 1:11
• Possible duplicate of orlp's answer – user45941 Apr 22 '16 at 4:11

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

# PARI/GP, 3332 26 bytes

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 L2 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))


 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!

• It's a byte shorter to cheat away the guard: n#x=sum[x^2+n#(x+2)|x^2<n] – xnor Apr 21 '16 at 17:52

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

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


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!

# 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. # Clojure, 53 bytes #(reduce +(map(fn[x](* x x))(range 1(Math/sqrt %)2)))  You can check it here: https://ideone.com/WKS4DA # 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. # 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 k2 is less than $i, if it is add k2 to \$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}


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


# Java 8, 128119117111 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


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


# 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

• Welcome to PPCG! Unnamed functions are acceptable too, so you can omit the c (unless you need it for recursion, which you don't). – Martin Ender Apr 21 '16 at 15:07
• @MartinBüttner okay thanks for the help – 8BitTRex Apr 21 '16 at 15:11
• You can omit the square brackets. This makes it the sum of a generator, which still works. – mbomb007 Apr 21 '16 at 15:13
• i**2 is longer than i*i, and you can shorten if i**2<n else 0 by putting the condition at the end: lambda n:sum(i*i for i in range(1,n,2)if i*i<n). You also don't have to show the old code, we can see that in the version history. – orlp Apr 21 '16 at 15:22