18
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ Neither of the close reasons on this are valid reasons to close a challenge... \$\endgroup\$ – user45941 Apr 24 '16 at 5:29

38 Answers 38

22
\$\begingroup\$

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).
| improve this answer | |
\$\endgroup\$
6
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
6
\$\begingroup\$

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

| improve this answer | |
\$\endgroup\$
6
\$\begingroup\$

Haskell, 30 bytes

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

Surprisingly normal-looking.

| improve this answer | |
\$\endgroup\$
4
\$\begingroup\$

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();}}}
| improve this answer | |
\$\endgroup\$
  • 4
    \$\begingroup\$ Welcome to Programming Puzzles and Code Golf! The agreed-upon format for answer headers here is # Language name, number bytes for consistency. \$\endgroup\$ – cat Apr 21 '16 at 11:56
  • 2
    \$\begingroup\$ Why do you Console.Read at the end? \$\endgroup\$ – Martin Ender Apr 21 '16 at 11:57
  • 1
    \$\begingroup\$ namespaces aren't required for single files. \$\endgroup\$ – ASCII-only Apr 21 '16 at 12:01
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – ASCII-only Apr 21 '16 at 12:04
  • 2
    \$\begingroup\$ @Thomas You can run your program with Ctrl+F5 in VS in which case the window will remain open after the program terminates. \$\endgroup\$ – Martin Ender Apr 21 '16 at 12:22
4
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
4
\$\begingroup\$

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!

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

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;}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ most verbose languages More golfy than Python, C#, LISP, Forth, etc, C is actually pretty good for golf \$\endgroup\$ – cat Apr 22 '16 at 0:59
  • \$\begingroup\$ @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. \$\endgroup\$ – James Apr 22 '16 at 1:03
3
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Will the next one be called Literally? \$\endgroup\$ – cat Apr 25 '16 at 20:14
3
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

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!

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Martin Ender Apr 21 '16 at 12:45
  • \$\begingroup\$ @MartinButtner Yes, you're right. I'll see if I can find an elegant fix \$\endgroup\$ – A Simmons Apr 21 '16 at 14:00
2
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Alternative (10 byte): s<#Q%2t^R2 \$\endgroup\$ – Leaky Nun Apr 22 '16 at 15:31
2
\$\begingroup\$

Mathcad, 31 "bytes"

enter image description here

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.

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

Racket, 57 bytes

(λ(n)(for/sum([m(map sqr(range 1 n 2))]#:when(< m n))m))
| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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)
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ bool is a subclass of int in Python, which means False is an acceptable value for 0. \$\endgroup\$ – cat Apr 22 '16 at 1:11
  • \$\begingroup\$ Possible duplicate of orlp's answer \$\endgroup\$ – user45941 Apr 22 '16 at 4:11
1
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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 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))
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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!

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

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.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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;
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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!

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Clojure, 53 bytes

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

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

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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)
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Welcome to PPCG! Unnamed functions are acceptable too, so you can omit the c (unless you need it for recursion, which you don't). \$\endgroup\$ – Martin Ender Apr 21 '16 at 15:07
  • \$\begingroup\$ @MartinBüttner okay thanks for the help \$\endgroup\$ – 8BitTRex Apr 21 '16 at 15:11
  • \$\begingroup\$ You can omit the square brackets. This makes it the sum of a generator, which still works. \$\endgroup\$ – mbomb007 Apr 21 '16 at 15:13
  • \$\begingroup\$ 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. \$\endgroup\$ – orlp Apr 21 '16 at 15:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.