6
\$\begingroup\$

Write a program that checks if a given positive integer can be represented as sum of two or more consecutive positive integers.

Example:

43 can be represented as 21 + 22

10 = 1+2+3+4

but 4 cannot be represented in this way.

Input spec: positive integer (as argument or stdin)

Output spec: truthy or falsy

Sample i/o

43 -> true
4 -> false

Shortest code wins.

\$\endgroup\$
8
  • \$\begingroup\$ I assume ./check 1 should return false? \$\endgroup\$
    – mellamokb
    Commented Jun 23, 2011 at 4:23
  • 1
    \$\begingroup\$ @mellamokb, I've fixed the spec and it's now clear that 1 gives false. \$\endgroup\$ Commented Jun 23, 2011 at 9:24
  • \$\begingroup\$ Is case important for the output? \$\endgroup\$
    – Joey
    Commented Jun 24, 2011 at 11:12
  • \$\begingroup\$ Not really, that should not be a problem :) \$\endgroup\$ Commented Jun 24, 2011 at 11:57
  • 1
    \$\begingroup\$ Related OEIS sequence \$\endgroup\$ Commented Dec 6, 2016 at 5:23

21 Answers 21

28
\$\begingroup\$

JavaScript (31)

alert(!!((n=~~prompt())&(n-1)))

From my testing, I believe this gives correct solutions.

http://jsfiddle.net/3e9FZ/

Edit: (SPOILER ALERT!) Here is the justification for this answer:

  1. All odd numbers greater than 1 can be trivially written as the sum of two consecutive numbers (ex 15 = 7+8, 23=11+12, etc.).
  2. For even numbers having an odd factor where the odd factor is less than twice the even factor. For example, 4*7, because 7 < (2*4 = 8). Simply add 7 numbers with 4 at the center, 1+2+3+4+5+6+7.
  3. For even numbers having an odd factor where the odd factor is more than twice the even factor. For example, 4*9, because 9 > (2 * 4 = 8). Double the even factor, and halve the odd factor to get 8*4.5. You will add the 8 numbers centered at 4.5, i.e., 1+2+3+4+5+6+7+8.
  4. The only numbers left are the even numbers having no odd factor, i.e., the powers of two. The formula for the sum of a consecutive set of numbers is (avg * count). Now if the count is odd, then avg is a whole number, and (avg * count) has an odd factor. If count is even, then avg must be #.5, and thus avg * 2 is odd, and so avg * count has an odd factor. Therefore, any sum using the formula (avg * count) must have an odd factor, which powers of two do not, and therefore have no solution.
\$\endgroup\$
13
  • 4
    \$\begingroup\$ It easy to see that odd numbers can be written as a sum of two consecutive numbers, and therefore any number that's not a power of two can be written as a sum of consecutive numbers. \$\endgroup\$
    – Alexandru
    Commented Jun 23, 2011 at 13:49
  • 2
    \$\begingroup\$ @Paul R: I have updated the answer with justification for why this should be correct. \$\endgroup\$
    – mellamokb
    Commented Jun 23, 2011 at 16:11
  • 4
    \$\begingroup\$ +1 for the proof (although to be pedantic, all odd numbers greater than 1). \$\endgroup\$ Commented Jun 23, 2011 at 16:28
  • 1
    \$\begingroup\$ @mellamokb: to be pedantic you still need to prove lack of solution for powers of two. \$\endgroup\$
    – Alexandru
    Commented Jun 23, 2011 at 16:42
  • 1
    \$\begingroup\$ Bloody brilliant \$\endgroup\$ Commented Aug 12, 2011 at 0:55
3
\$\begingroup\$

Golfscript, 20 chars

~.(&!!"falsetrue"5/=

Someone had to.

\$\endgroup\$
3
\$\begingroup\$

Ruby (23)

only 3 chars longer than golfscript :)

p 0<(n=$*[0].to_i)&n-1

output:

$ ruby gc2958.rb 4
false
$ ruby gc2958.rb 43
true
$ wc gc2958.rb
  1       2      23 gc2958.rb
\$\endgroup\$
2
\$\begingroup\$

Haskell, 74

Felt like doing the brute force way.

import List
main=print.f=<<readLn
f n=elem n$map sum$tails=<<inits[1..n-1]
\$\endgroup\$
1
\$\begingroup\$

JavaScript (81)

n=prompt(r=i=1)|0;while(r&++i*i/2<n)if(i%2&!(n%i)|!(i%2|(n+i/2)%i))r=!r;alert(!r)

I'm cheating with & and | - even though they are technically bit-wise operations, they do the job quite nicely because the result is a 1/0 which are valid conditionals!

http://jsfiddle.net/HCqK2/4/

\$\endgroup\$
1
\$\begingroup\$

C, 67

As mellamokb suggested all numbers, except powers of two, can be written as sum of positive consecutive numbers:

main(int i,char**a){
printf((i=atoi(a[1]))&i-1?"true\n":"false\n");
}
\$\endgroup\$
1
  • \$\begingroup\$ your kinda stealing his idea... \$\endgroup\$ Commented Oct 21, 2013 at 17:12
1
\$\begingroup\$

C

return 1 or 0:

int i(int j){return((j%2)?!(j==1):i(j/2));}
\$\endgroup\$
1
  • 3
    \$\begingroup\$ doesnt fulfill the task - it has to output "true" or "false". \$\endgroup\$
    – Rommudoh
    Commented Aug 11, 2011 at 12:50
1
\$\begingroup\$

Mathematica, 23 bytes

N[2~Log~#]~MatchQ~_Real

For once it's actually useful

\$\endgroup\$
1
\$\begingroup\$

TI-Basic, 6 bytes

fPart(logBASE(Ans,2

Operating system ≥2.53 required due to logBASE(. Without logBASE, there are alternatives:

7 bytes: fPart(ln(Ans)/ln(2
7 bytes: fPart(log(Ans)/log(2
\$\endgroup\$
1
\$\begingroup\$

Befunge-93, 28 bytes

Try it Online!

&[email protected]<@.0<
:</2_^#!_^#-1\%2:

Instead of checking if the given integer is an element in this sequence, it's much easier to check if it isn't in the complimentary sequence (powers of 2 with 0 instead of 1). This functions very similarly to mellamokb's answer in that sense.

Note that the linked sequences are not exact representations of all truthy/falsey results of each integer, because the sequence uses non-negative integers instead of strictly positive. Thus, 1 is in the linked sequence, even though for this specific problem it should be in its compliment.

\$\endgroup\$
4
  • \$\begingroup\$ not actually the powers of two... It is actually the powers of two with 1 replaced by 0 \$\endgroup\$ Commented Dec 6, 2016 at 6:16
  • \$\begingroup\$ also you are using the wrong sequence. that one includes 1 as a number by virtue of 1+0, as it uses non negative rather than positive \$\endgroup\$ Commented Dec 6, 2016 at 6:29
  • \$\begingroup\$ @DestructibleWatermelon I realize that the sequence doesn't completely match the problem, but only in regards to the base case of 1. The complimentary sequence for the one that matches the problem is the powers of 2 (possibly in addition to 0, depending on where the sequence starts). \$\endgroup\$ Commented Dec 6, 2016 at 6:48
  • \$\begingroup\$ Why don't you just use the actual powers of two instead of that sequence of two? (0 is not a positive number anyway, so no need to cover it) \$\endgroup\$ Commented Dec 6, 2016 at 6:53
1
\$\begingroup\$

Wren, 18 17 bytes

Umm, it's shorter than GolfScript...

Fn.new{|n|n&-n<n}

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Python 2 REPL, 24 chars

Shortest python atm, borrowing bin() from @Fraxtil :)

bin(input()).count('1')>1
\$\endgroup\$
3
  • 1
    \$\begingroup\$ bin(input()).count('1')>=2? \$\endgroup\$ Commented Sep 5, 2012 at 4:18
  • 1
    \$\begingroup\$ Haha, that's kinda obvious really :D thanks. And >=2 == >1 ;) \$\endgroup\$
    – daniero
    Commented Sep 5, 2012 at 15:37
  • 1
    \$\begingroup\$ Is this not repl snippet? \$\endgroup\$ Commented Dec 6, 2016 at 0:38
1
\$\begingroup\$

Python 2 REPL, 19 17 16

x=input()
x>x&-x
\$\endgroup\$
4
  • 1
    \$\begingroup\$ Nice. You can actually shave off two characters on the second line: ~-x&x>0 \$\endgroup\$
    – daniero
    Commented Oct 22, 2013 at 18:18
  • \$\begingroup\$ @daniero Nice trick!! \$\endgroup\$
    – Coding man
    Commented Oct 22, 2013 at 19:07
  • \$\begingroup\$ x&-x<x saves yet 1 character \$\endgroup\$
    – AMK
    Commented Oct 23, 2013 at 15:07
  • \$\begingroup\$ @AMK great trick!! updated the code. \$\endgroup\$
    – Coding man
    Commented Oct 23, 2013 at 17:50
1
\$\begingroup\$

Python 3 REPL, 34

bool(int(bin(2*int(input()))[3:]))

I took an alternative approach to the solution, but can't seem to squeeze anything else out of it. This code takes the input, multiplies it by two (this fixes the input case of 1 which breaks otherwise), converts it to binary, strips out the first 3 characters (0b1), converts the remainder to an integer (which is 0 iff the input was a power of two), and then converts that to a boolean.

As mentioned above, you can remove the 2* to get a 32-char solution that fails on an input of 1 but is otherwise perfect.

\$\endgroup\$
1
  • \$\begingroup\$ i assume you need a truthy value, so the bool() is not needed? \$\endgroup\$ Commented Jul 30, 2022 at 13:18
1
\$\begingroup\$

Dyalog APL, 7 bytes

0≠1|2∘⍟

Checks if a number is not a power of 2.

Attempt This Online!

    2∘⍟  log base 2 of
  1|     mod 1
0≠       is not zero

My 14-byte brute-force attempt before learning that the question is equivalent to asking if a number is not a power of 2:

⊢∊∘∊1↓+/¨∘⊂⍥⍳⍨

Using 3 as an example:

             ⍨  put the argument on both sides: 3 ... 3
           ⍥⍳   integers from 1 to n on both sides: 1 2 3 ... 1 2 3
      +/¨∘⊂     sums of length-1, 2, and 3 windows in 1 2 3: (1 2 3)(3 5)(6)
    1↓          drop the length-1 sums
   ∊            flatten into a list
⊢∊∘             is the argument in this list?
\$\endgroup\$
1
\$\begingroup\$

Vyxal, 2 bytes

‹⋏

Try it Online!

Just a port of Jelly and JS. Bitwise AND with n-1. Returns positive integer for true, 0 for false.

Prolog (SWI), 13 bytes

\N:-0<N-1/\N.

Try it online!

-4 thanks to Jo King

\$\endgroup\$
1
  • \$\begingroup\$ the prolog could just be 0<N-1/\N \$\endgroup\$
    – Jo King
    Commented Sep 4, 2022 at 11:07
0
\$\begingroup\$

J, 12

It doesn't follow the spec 'true'/'false'. Rather I stick with 1/0. It checks if log base 2 of a number has a decimal mark.

+/=&'.'":2^.

   +/=&'.'":2^.1
0
   +/=&'.'":2^.4
0
   +/=&'.'":2^.43
1
\$\endgroup\$
0
\$\begingroup\$

Jelly, 2 bytes

&’

Try it online!

Just a translation of the accepted JavaScript solution.

\$\endgroup\$
0
\$\begingroup\$

Perl, 51 bytes

print(((log($ARGV[0])/log(2))=~ /\./ )?true:false);

Example:

$perl Soc.pl 45

true

$perl Soc.pl 8

false
\$\endgroup\$
0
0
\$\begingroup\$

Python 2 REPL, 33 chars

It seems that there's a way shorter way to do this though:

s=input()
n=2
while n<s:n*=2
n!=s
\$\endgroup\$
0
\$\begingroup\$

Vyxal, 10 bytes

Ṅ's¯1J≈;Ṫḃ

Try it Online!

A non-bitwise answer that doesn't port Javascript.

Explained

Ṅ's¯1J≈;Ṫḃ
Ṅ           # Integer partitions of the input
 '     ;    # Filtered by:
  s¯        #  Are the deltas of the sorted partition
    1J≈     #  All 1?
        Ṫḃ  # Remove the tail of the list because that's just the input as a single item and then return whether there's any items in the list.
\$\endgroup\$
1
  • \$\begingroup\$ You can use instead of Ṫḃ (using reversed booleans). \$\endgroup\$
    – naffetS
    Commented Jul 30, 2022 at 2:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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