Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #105842

Re: Program to find consecutive integers

Show all headers | View raw

Jens Thoms Toerring <jt@toerring.de> wrote:
> insane_goat <nobody@nothing.net> wrote:
> > On 2017-03-10, Joe Pfeiffer <pfeiffer@cs.nmsu.edu> wrote:
> > > 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';-)

> 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  ___      jt@toerring.de
   \__________________________      http://toerring.de

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Program to find consecutive integers insane_goat <nobody@nothing.net> - 2017-03-10 04:21 +0000
  Re: Program to find consecutive integers Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2017-03-09 22:26 -0700
    Re: Program to find consecutive integers insane_goat <nobody@nothing.net> - 2017-03-10 06:48 +0000
      Re: Program to find consecutive integers Ike Naar <ike@iceland.freeshell.org> - 2017-03-10 08:18 +0000
        Re: Program to find consecutive integers insane_goat <nobody@nothing.net> - 2017-03-10 08:48 +0000
          Re: Program to find consecutive integers Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-03-10 10:38 +0000
            Re: Program to find consecutive integers insane_goat <nobody@nothing.net> - 2017-03-12 13:15 +0000
              Re: Program to find consecutive integers Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-03-12 13:29 +0000
            Re: Program to find consecutive integers raltbos@xs4all.nl (Richard Bos) - 2017-03-14 07:49 +0000
          Re: Program to find consecutive integers Öö Tiib <ootiib@hot.ee> - 2017-03-10 05:12 -0800
        Re: Program to find consecutive integers jameskuyper@verizon.net - 2017-03-10 07:16 -0800
          Re: Program to find consecutive integers Ike Naar <ike@iceland.freeshell.org> - 2017-03-10 19:20 +0000
            Re: Program to find consecutive integers James Kuyper <jameskuyper@verizon.net> - 2017-03-10 15:21 -0500
              Re: Program to find consecutive integers Ike Naar <ike@iceland.freeshell.org> - 2017-03-10 20:36 +0000
              Re: Program to find consecutive integers insane_goat <nobody@nothing.net> - 2017-03-12 13:19 +0000
                Gotta keep up with the times (Was: Program to find consecutive integers) gazelle@shell.xmission.com (Kenny McCormack) - 2017-03-12 13:25 +0000
                Re: Gotta keep up with the times (Was: Program to find consecutive integers) Malcolm McLean <malcolm.mclean5@btinternet.com> - 2017-03-12 08:11 -0700
                Re: Gotta keep up with the times (Was: Program to find consecutive integers) gazelle@shell.xmission.com (Kenny McCormack) - 2017-03-12 15:53 +0000
                Re: Gotta keep up with the times (Was: Program to find consecutive integers) Malcolm McLean <malcolm.mclean5@btinternet.com> - 2017-03-12 10:50 -0700
                Re: Gotta keep up with the times (Was: Program to find consecutive integers) gazelle@shell.xmission.com (Kenny McCormack) - 2017-03-12 18:25 +0000
                Re: Gotta keep up with the times (Was: Program to find consecutive integers) Malcolm McLean <malcolm.mclean5@btinternet.com> - 2017-03-12 16:20 -0700
                Re: Gotta keep up with the times gordonb.g2pqz@burditt.org (Gordon Burditt) - 2017-03-14 01:09 -0500
                Re: Gotta keep up with the times raltbos@xs4all.nl (Richard Bos) - 2017-03-14 07:43 +0000
                Re: Program to find consecutive integers "James R. Kuyper" <jameskuyper@verizon.net> - 2017-03-12 10:28 -0400
            Re: Program to find consecutive integers Gareth Owen <gwowen@gmail.com> - 2017-03-11 07:42 +0000
      Re: Program to find consecutive integers jt@toerring.de (Jens Thoms Toerring) - 2017-03-10 10:21 +0000
        Re: Program to find consecutive integers Nathan Wagner <nw@hydaspes.if.org> - 2017-03-10 22:07 +0000
          Re: Program to find consecutive integers Nathan Wagner <nw@hydaspes.if.org> - 2017-03-10 22:20 +0000
          Re: Program to find consecutive integers jr <creature.eternal@gmail.com> - 2017-03-10 23:49 -0800
        Re: Program to find consecutive integers jt@toerring.de (Jens Thoms Toerring) - 2017-03-11 23:38 +0000
          Re: Program to find consecutive integers Tim Rentsch <txr@alumni.caltech.edu> - 2017-04-16 21:18 -0700

csiph-web