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

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

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? Apr 21 '16 at 11:57
• namespaces aren't required for single files. 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. 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. 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. Apr 21 '16 at 13:52
• @Dennis Ahh! And alert too, apparently... Apr 21 '16 at 13:53
• 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! Feb 16 '18 at 16:24
• This site is awesome, thanks! 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. 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;
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. 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. Apr 21 '16 at 12:45
• @MartinButtner Yes, you're right. I'll see if I can find an elegant fix 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 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. 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!

$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). Apr 21 '16 at 15:07
• @MartinBüttner okay thanks for the help Apr 21 '16 at 15:11
• You can omit the square brackets. This makes it the sum of a generator, which still works. 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