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

Groups > comp.lang.c > #105706 > unrolled thread

Program to find consecutive integers

Back to article view | Back to comp.lang.c

Contents

  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

Page 2 of 2 — ← Prev page 1 [2]

#105895 — Re: Gotta keep up with the times (Was: Program to find consecutive integers)

On Sunday, March 12, 2017 at 6:25:58 PM UTC, Kenny McCormack wrote:
> In article <d21f9712-bba3-4c0f-bbaf-5b1cd84fb95d@googlegroups.com>,
> 
>     1) That by 'present if different', you meant 'present in different'.
>
Yes, it's not true that teaching adults, especially less able adults,
is school teaching with a ll the problems removed. But in many ways
it is easier.
>
>     2) That the UK has evolved the same "everybody goes to college"              
?        mindset as the US.  Such that everybody assumes that if you 
>        don't go to college, the only job you'll ever have is flipping
>        burgers.  I imagine that it won't be that much longer until 
>        you can't get a job flipping burgers w/o a college degree.
> 
>
Exactly. Recently a friend's son went to university to study history.
He clearly wasn't academic material and I made concerns known to
his father. But Dad was impatient with what I was saying about
his schoolwork - he's got to take exams because that's what they do
at school - and on college he acknowledged by point but asked for an
alternative. And there just isn't anything very obvious.

But the boy dropped out after the first year, landing him with over
ten thousand pounds in debt, and a black mark rather than a credit 
on his CV. He was doing bar work when I last asked about him.  
>
> (Moving onto a new, but related topic)
> Paul Graham's thesis is that all education below college level is just
> "warehousing" - i.e., day care.
> 
That might be more true in the US than here. Here, if you can possibly
afford it and the child shows a glimmering of intelligence, you go
private. That's ten thousand a year, often a lot more. Parents want
more than warehousing for that sort of money. Unfortunately, whilst
parents value certification, they don't normally attach much value to
any academic subject for its own sake. CLC regs are an exception,
they can point to computer programming / maths.

[toc] | [prev] | [next] | [standalone]

#105987 — Re: Gotta keep up with the times

> I get it, but, point of order, I don't think you're allowed to use the 'R
> word' nowadays.  Instead, we use the updated term 'Trump Voter' (or,
> equivalently, 'Trump Supporter').  It means the same thing.

That's a very USA-centric view.  And "Voter" and "Supporter" are not
at all equivalent.

In the USA, there are lots of stupid teenagers in High Schools.
Most of them are not old enough to vote (Seniors and those who got
kept back or put back a grade may be 18 or older).  They may support
Trump in spirit and even may give him campaign contributions, but
they didn't vote for him.

Lots of people in other countries (like those in Europe, Asia,
Africa, Australia, South America, plus Mexico and Canada) may not
care about Trump.  In Antarctica, you're either a tourist or a
member of a scientific expedition, and you vote in your home country,
if you get to vote at all.  They are more concerned with political
issues in their own countries, such as whether the death penalty
is enough for C programmers who void main(), or mandating the One
True Brace Style.

There are lots of people eligible to vote in the USA who didn't
bother, especially with the choice of candidates in the last election.
I kept praying it was all a joke, and the Republicans were going
to take back their nomination of Trump and put up Abraham Lincoln,
and that the Democrats were going to take back their nomination of
Hillary Clinton and put up JFK.  Yes, I know both of them are dead.
That's a very desirable attribute of a candidate.  Dead candidates
tend not to embarass themselves by contradicting what they said
earlier, or just making fools of themselves.  They also tend to
vote for less totally stupid legislation.

I don't think some of the people in other countries who allegedly
go out of their way to try to rig the election, because they want
to destroy the USA and see Trump as being one way to do it, are
necessarily fools.  You may not like their objectives, but they can
accomplish their stated objectives by getting Trump elected.  Those
Russians who allegedly tried to rig the election for their political
advantage don't have to live in the USA.  Neither do the members
of ISIS who have chosen "Death (by Trump) To America" as the method
of its death.

[toc] | [prev] | [next] | [standalone]

#105993 — Re: Gotta keep up with the times

gordonb.g2pqz@burditt.org (Gordon Burditt) wrote:

> > I get it, but, point of order, I don't think you're allowed to use the 'R
> > word' nowadays.  Instead, we use the updated term 'Trump Voter' (or,
> > equivalently, 'Trump Supporter').  It means the same thing.
> 
> That's a very USA-centric view.  And "Voter" and "Supporter" are not
> at all equivalent.

How about "attribution-remover", then?

Richard

(For the record: permission to quote my posts without the proper
attribution is explicitly denied.)

[toc] | [prev] | [next] | [standalone]

#105864

On 03/12/2017 09:19 AM, insane_goat wrote:
...
> I use unsigned int in my program. I assumed it was quite clear, as only a
> complete retard would use unsigned integers when he wanted signed answers.

I've seen people do stupider things than that.
When you specify the problem to be solved as poorly as you did, I can't 
assume that the code you've written actually solves the fully-specified 
problem - I've seen too many people post questions here about code that 
did something quite different from what it was intended to do.

[toc] | [prev] | [next] | [standalone]

#105785

Ike Naar <ike@iceland.freeshell.org> writes:

> On 2017-03-10, jameskuyper@verizon.net <jameskuyper@verizon.net> wrote:
>> Other possibilities include:
>> {-14, -13, -12, -11, -10, -9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1,
>> 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}
>>
>> I suspect that this is not what insane_goat meant, but until he
>> specifies the problem to be solved more precisely, this seems to
>> qualify.
>
> I was assuming that all numbers were meant to be positive integers.


Let M = 2^N * (odd prime factors)

For every odd factor (not necessarily prime), f of M there's a sequence
length f centred on M/f and a sequence length f*2^(N+1) centred on
M/(f*2^(N+1))

For M=15, odd factors 1,3,5,15
f=1  {15},               {7,8}
f=3  {4,5,6},            {0,1,2,3,4,5}
f=5  {1,2,3,4,5},        {-3,...6}
f=15 {-6...8}            {-14,....15}

For M=8, odd factors 1
Only solutions
f=1 {8}                   {-7...8}

For M=24, odd factors 1,3
f=1 {24}                  {-6..9}
f=3 {7,8,9}               {-23..24}

etc, etc, etc

So all you need to is factorise ... which may be harder than you think

[toc] | [prev] | [next] | [standalone]

#105719

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.

That's still underspecified. What's the minimum number of
consecutive integers that must make up the target number?
Your program doesn't seem to be satisfied with only 2, but
all odd numbers (except 1) can be represented as the sum
of two consecutive numbers.

And do you want to find all possible solution or are you
happy when you found the very first one? There are lots
of cases with several solutions, e.g. for 15 you have

1 2 3 4 5
4 5 6
7 8

But your program will only find the first one.

What you definitely can do without is the memory alloca-
tion (and setting it to 0 each round through an inner
loop) - you just have to "remember" the start and the
end of the sequence to print out all the numbers.

And your handling of argv[1] is a bit dangerous. It doesn't
recognize properly when it's no number at all, and for
negative numbers you end up with a huge taget value.

Here's my version of your program. It probably isn't any
faster (but it at least has one less level of loop nesting).
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;-) It also prints out solutions
that consist of two consecutive numbers only and prints
out all possible sequences (which will make it slower than
yours since it does more work).

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

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);
    int found = 0;

    for (unsigned begin = 1; begin <= target / 2; ++begin) {
        unsigned end = begin + 1;
        unsigned answer = begin + end;

        while (answer < target)
            answer += ++end;

        if (answer > target)
            continue;

        found++;
        for (unsigned i = begin; i < end; ++i)
            printf("%u ", i);
        printf("%u\n", end);
//      break;            // uncomment to get only the first solution
    }

    if (! found)
        puts("no answer");
        return EXIT_FAILURE;
    }

    return EXIT_SUCCESS;
}
                     Regards, Jens
-- 
  \   Jens Thoms Toerring  ___      jt@toerring.de
   \__________________________      http://toerring.de

[toc] | [prev] | [next] | [standalone]

#105767

On 2017-03-10, Jens Thoms Toerring <jt@toerring.de> wrote:
> insane_goat <nobody@nothing.net> wrote:
> And do you want to find all possible solution or are you
> happy when you found the very first one? There are lots
> of cases with several solutions, e.g. for 15 you have
>
> 1 2 3 4 5
> 4 5 6
> 7 8

> Here's my version of your program. It probably isn't any
> faster (but it at least has one less level of loop nesting).
> 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;-)

With that in mind, I observe:

solutions of any length L starting at b have the sum

b * ( (L+1)*L/2 ),
since that sum must equal the target number, and the base b must be a positive
integer, some algebra leads to the following...

No attempt at error checking of the argument string or target value for
possible overflow is made.  There may be bugs, so if you use this for your
Mars rocket, don't blame the resulting crash on me.

int main(int ac, char *av[]) {
        unsigned target; /* number to decompose */
        unsigned sbase; /* lowest number in solution */
        unsigned slen; /*  N quantity of numbers in solution */
        int oddtarget;
        unsigned maxlen;

        target = atoi(av[1]);

        maxlen = (sqrt(8.0*target+1.0)-1) / 2;
        oddtarget = target % 2;

        if (oddtarget) {
                printf(" %d %d\n", target/2, target/2+1);
        }

        for (slen=3; slen <= maxlen; slen++) {
                int i;

                if (oddtarget && slen % 2 != 1) {
                        continue; /* odd target solutions have odd length */
                }

                sbase = (2 * target / slen - slen + 1) / 2;

                if (2 * target % slen != 0) {
                        continue; /* solution base must be integral */
                }
                if ( (2 * target / slen - slen + 1) % 2 != 0) {
                        continue;
                }

                for (i=0; i<slen; i++) {
                        printf(" %d", sbase+i);
                }
                printf("\n");
        }

        return 0;
}

arbela:~ nw$ ./targ 42
 13 14 15
 9 10 11 12
 3 4 5 6 7 8 9
arbela:~ nw$ 

Looks good, must be perfect.

-- 
nw

[toc] | [prev] | [next] | [standalone]

#105768

On 2017-03-10, Nathan Wagner <nw@hydaspes.if.org> wrote:
> With that in mind, I observe:
>
> solutions of any length L starting at b have the sum
>
> b * ( (L+1)*L/2 ),

Er, no they don't, they have sum

L * ( L-1 + 2*b ) / 2

-- 
nw

[toc] | [prev] | [next] | [standalone]

#105786

On Friday, 10 March 2017 22:07:41 UTC, Nathan Wagner  wrote:
> Looks good, must be perfect.

expcept for exact powers of two.  :-)

[toc] | [prev] | [next] | [standalone]

#105842

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

[toc] | [prev] | [next] | [standalone]

#108195

jt@toerring.de (Jens Thoms Toerring) writes:

> 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";-)
>
> [...]

I didn't try to use any fancy mathematics.  The program below
is a cleaned-up version of my first program to solve the
problem (the first version had 8 lines in main() rather than
the 7 shown here).  Counting the number of solutions I leave
as an exercise for the reader. :)



#include <stdio.h>
#include <stdlib.h>

int
main( int argc, char *argv[] ){
    unsigned long n = argc > 1 ? strtoul( argv[1], 0, 10 ) : 1234567890;
    unsigned long p, q, s;
    for(  p = q = s = 0;  p <= n/2;  s = s > n ?  s - p++ : s + q++  ){
        if(  s != n  )  continue;
        printf( " %12lu  %6lu:  %12lu .. %lu\n", n, q-p, p, q-1 );
    }
    return  0;
}

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

Back to top | Article view | comp.lang.c

csiph-web