*Post by Jens Thoms Toerring**Post by insane_goat**Post by Joe Pfeiffer*Umm.... you're going to have to give a more complete description of the

problem statement before I, at any rate, will want to think about your

program.

Sorry. I was in a bit of a rush.

I meant consecutive integers which add up to the target.

Here's my version of your program. It probably isn't any

faster (but it at least has one less level of loop nesting).

Actually, it's quite a bit faster, even printing out all

possible sequences, at least for larger values of 'target';-)

*Post by Jens Thoms Toerring*Perhaps one could speed it up a bit by using Gauss' formula

(i.e., the sum of all numbers from 1 to n is n*(n+1)/2) but

I'm too lazy to work it out;-)

No luck with that yet - one has to solve a quadratic equation

and once you start using floats things get rather slow, killing

the theoretical gains (at least on my machine).

But here's an optimized version. It uses that, once you've

found the first (longest) sequence with a length of say N,

you don't need to check for all larger values of 'begin',

but the next possible successful value for 'begin' can't be

smaller than 'target/N - N/2'. So you can often skip some

of the tests. No guarantees though that it's correct, it

contains bits of "experimental mathematics";-)

#include <stdio.h>

#include <stdlib.h>

#include <ctype.h>

static int found = 0;

static unsigned find_seq(unsigned target,

unsigned * begin,

unsigned max)

{

for (; *begin < max; ++*begin) {

unsigned end = *begin + 1;

unsigned answer = *begin + end;

while (answer < target)

answer += ++end;

if (answer > target)

continue;

found++;

printf("%u - %u (%u)\n", *begin, end, end - *begin + 1);

return end - *begin + 1;

}

return 0;

}

int main(int argc, char *argv[])

{

if (argc < 2) {

fprintf(stderr, "usage: %s <target>\n", argv[0]);

return EXIT_FAILURE;

}

const char *p = argv[1];

while (isblank(*p))

p++;

if (! *p || ! isdigit(*p)) {

fprintf(stderr, "target must be a non-negative number\n");

return EXIT_FAILURE;

}

const unsigned target = (unsigned) atoi(p);

const unsigned max = (target % 2) ?

(target / 2 + 1) : (target / 3 + target % 3);

unsigned start = 1;

/* Try to find the first (and longest) sequence */

unsigned len = find_seq(target, &start, max);

if (len == 0) {

puts("no sequence found");

return EXIT_FAILURE;

}

/* If the length of the sequence is 2 for odd or 3 for even targets

* we're done, there can't be any shorter one. */

if (len == 2 || (target % 2 == 0 && len == 3)) {

puts("1 sequence found\n");

return EXIT_SUCCESS;

}

/* Check for sequences with lower lengths down to 3, avoid repeating

* tests while skipping impossible ones. */

while (--len >= 3) {

unsigned new_start = target / len - len / 2;

start = start + 1 > new_start ? start + 1 : new_start;

unsigned int new_len = find_seq(target, &start, start + len / 2 + 1);

if (new_len)

len = new_len;

}

/* For odd targets there's always the trivial sequence of length 2. */

if (target % 2) {

found++;

printf("%u - %u (2)\n", target / 2, target / 2 + 1);

}

printf("\n%d sequence%s found\n", found, found > 1 ? "s" : "");

return EXIT_SUCCESS;

}

Regards, Jens

--

\ Jens Thoms Toerring ___ ***@toerring.de

\__________________________ http://toerring.de