Discussion:
Program to find consecutive integers
Add Reply
insane_goat
2017-03-10 04:21:10 UTC
Reply
Permalink
Raw Message
I wrote this small program to find consecutive integers up to the target. I
am quite sure that there are some ways to speed it up, can anyone suggest
improvements?

-- begin --

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

/*
* Find consecutive integers which add up to target
*/

int main(int argc, char *argv[])
{
if (argc < 2) {
fprintf(stderr, "usage: %s <target>\n", argv[0]);
return EXIT_FAILURE;
}

const unsigned target = (unsigned) atoi(argv[1]);
const unsigned max = target / 2;
const unsigned max_consecs = max;
unsigned answer;
unsigned *nums;

if ((nums = calloc(max_consecs, sizeof(int))) == NULL) {
perror("calloc");
return EXIT_FAILURE;
}

for (unsigned begin = 1; begin < max; ++begin) {
for (unsigned consecs = 2; consecs < max_consecs; ++consecs) {
answer = 0;
memset(nums, 0, max_consecs * sizeof(int));

for (unsigned i = 0; i < consecs; ++i) {
nums[i] = i + begin;

if ((answer += nums[i]) > target) {
break;
}
}

if (answer == target) {
for (unsigned i = 0; nums[i] != 0; ++i) {
if (i != 0) {
putchar(' ');
}

printf("%d", nums[i]);
}

putchar('\n');
free(nums);
return EXIT_SUCCESS;
} else if (answer > target) {
break;
}
}
}

puts("no answer");

free(nums);
return EXIT_FAILURE;
}

-- end --
--
insane_goat
Joe Pfeiffer
2017-03-10 05:26:05 UTC
Reply
Permalink
Raw Message
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. To me, producing consecutive integers boils down to

for (i = start; i <= end; i++)
printf("%\n", i);
insane_goat
2017-03-10 06:48:19 UTC
Reply
Permalink
Raw Message
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.
Post by Joe Pfeiffer
To me, producing consecutive integers boils down to
for (i = start; i <= end; i++)
printf("%\n", i);
--
Daniel Roskams
Ike Naar
2017-03-10 08:18:27 UTC
Reply
Permalink
Raw Message
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.
To me, producing consecutive integers boils down to
for (i = start; i <= end; i++)
printf("%\n", i);
Sorry. I was in a bit of a rush.
I meant consecutive integers which add up to the target.
The following sets of consecutive integers add up to the target 15:
{1,2,3,4,5}
{4,5,6}
{7,8}
{15}

Your algorithm produces the set {1,2,3,4,5},
Joe's algorithm produces the set {15}.

Why is your solution better than Joe's ?
insane_goat
2017-03-10 08:48:45 UTC
Reply
Permalink
Raw Message
Post by Ike Naar
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.
To me, producing consecutive integers boils down to
for (i = start; i <= end; i++)
printf("%\n", i);
Sorry. I was in a bit of a rush.
I meant consecutive integers which add up to the target.
{1,2,3,4,5}
{4,5,6}
{7,8}
{15}
Your algorithm produces the set {1,2,3,4,5},
Joe's algorithm produces the set {15}.
Why is your solution better than Joe's ?
Because it can find consecutive integers adding up to e.g. 296, which cannot
be produced by starting from 1.
--
Daniel Roskams
Ben Bacarisse
2017-03-10 10:38:35 UTC
Reply
Permalink
Raw Message
Post by insane_goat
Post by Ike Naar
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.
To me, producing consecutive integers boils down to
for (i = start; i <= end; i++)
printf("%\n", i);
Sorry. I was in a bit of a rush.
I meant consecutive integers which add up to the target.
{1,2,3,4,5}
{4,5,6}
{7,8}
{15}
Your algorithm produces the set {1,2,3,4,5},
Joe's algorithm produces the set {15}.
Why is your solution better than Joe's ?
Because it can find consecutive integers adding up to e.g. 296, which cannot
be produced by starting from 1.
296 is the sum of the sequence (296). The full statement of your
problem will either include some restrictions (for example the sequence
must be longer than 1 or the largest number in it must be less than some
limit) or some criterion for the best solution (the longest, the
shortest, etc) or maybe the requirement to produce (or count) all the
solutions. You are probably working from some external problem
statement. Can you link to it?

One thing to note is that your code allocated storage and did a lot of
adding things up (sorry, I did not study it) but you'll find a little
bit of mathematics goes a long way in this case.

Yours is not really a C question, but a C-related question is why are
you using C? (Not a trick question, I'm genuinely interested.)
--
Ben.
insane_goat
2017-03-12 13:15:16 UTC
Reply
Permalink
Raw Message
Post by Ben Bacarisse
Post by insane_goat
Post by Ike Naar
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.
To me, producing consecutive integers boils down to
for (i = start; i <= end; i++)
printf("%\n", i);
Sorry. I was in a bit of a rush.
I meant consecutive integers which add up to the target.
{1,2,3,4,5}
{4,5,6}
{7,8}
{15}
Your algorithm produces the set {1,2,3,4,5},
Joe's algorithm produces the set {15}.
Why is your solution better than Joe's ?
Because it can find consecutive integers adding up to e.g. 296, which cannot
be produced by starting from 1.
296 is the sum of the sequence (296). The full statement of your
problem will either include some restrictions (for example the sequence
must be longer than 1
Yes, it was this requirement.
Post by Ben Bacarisse
or the largest number in it must be less than some
limit) or some criterion for the best solution (the longest, the
shortest, etc) or maybe the requirement to produce (or count) all the
solutions. You are probably working from some external problem
statement. Can you link to it?
It was in a math test somewhere. I don't remember the exact wording but it was
something like "find the only set of more than 1 consecutive integers which
add up to 296".
Post by Ben Bacarisse
One thing to note is that your code allocated storage and did a lot of
adding things up (sorry, I did not study it) but you'll find a little
bit of mathematics goes a long way in this case.
Yours is not really a C question, but a C-related question is why are
you using C? (Not a trick question, I'm genuinely interested.)
I decided it was an interesting 20-minute thing to do when I was bored. That's
all.
--
Daniel Roskams
Ben Bacarisse
2017-03-12 13:29:13 UTC
Reply
Permalink
Raw Message
Post by insane_goat
Post by Ben Bacarisse
Post by insane_goat
Post by Ike Naar
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.
To me, producing consecutive integers boils down to
for (i = start; i <= end; i++)
printf("%\n", i);
Sorry. I was in a bit of a rush.
I meant consecutive integers which add up to the target.
{1,2,3,4,5}
{4,5,6}
{7,8}
{15}
Your algorithm produces the set {1,2,3,4,5},
Joe's algorithm produces the set {15}.
Why is your solution better than Joe's ?
Because it can find consecutive integers adding up to e.g. 296, which cannot
be produced by starting from 1.
296 is the sum of the sequence (296). The full statement of your
problem will either include some restrictions (for example the sequence
must be longer than 1
Yes, it was this requirement.
... and positive integers only.

<snip>
Post by insane_goat
Post by Ben Bacarisse
Yours is not really a C question, but a C-related question is why are
you using C? (Not a trick question, I'm genuinely interested.)
I decided it was an interesting 20-minute thing to do when I was bored. That's
all.
That makes sense. I tend to use a language with a REPL for this sort of
"playing about" code because you can experiment more freely. (That and
you usually get large integers built-in, not that that's likely to be
significant in this case.)
--
Ben.
Richard Bos
2017-03-14 07:49:11 UTC
Reply
Permalink
Raw Message
Post by Ben Bacarisse
Yours is not really a C question, but a C-related question is why are
you using C? (Not a trick question, I'm genuinely interested.)
This is, in fact, a problem which is very much solvable in your head,
and IMO a very elegant one for doing so as well, if you think a bit
about the divisibility of N subsequent positive integers.

(Hint: nal A fhofrdhrag vagrtref ner qvivfvoyr ol A, jvgu jung
erznvaqre? Gurer ner gjb nafjref sbe gjb boivbhf frgf bs vagrtref.)

Of course, if you want to do it in C, not to solve the problem, but to
learn C, that's a valid option, too. But even then there are more
elegant and less elegant solutions.

Richard
Öö Tiib
2017-03-10 13:12:17 UTC
Reply
Permalink
Raw Message
Post by insane_goat
Post by Ike Naar
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.
To me, producing consecutive integers boils down to
for (i = start; i <= end; i++)
printf("%\n", i);
Sorry. I was in a bit of a rush.
I meant consecutive integers which add up to the target.
{1,2,3,4,5}
{4,5,6}
{7,8}
{15}
Your algorithm produces the set {1,2,3,4,5},
Joe's algorithm produces the set {15}.
Why is your solution better than Joe's ?
Because it can find consecutive integers adding up to e.g. 296, which cannot
be produced by starting from 1.
That is all true but so what? Joe's answer did not seemingly start
from 0 but from "start". Your requirements do not specify where that
start is. It can't be 1 always but so what? Let me write little example
program based on Joe's answer (and mine choice of "start" and "end"):

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

void consecutive( int target )
{
int start, end, sum, i;
if ( target == 0 )
{
start = -42;
end = 42;
}
else if ( target < 0 )
{
start = target;
end = - 1 - target;
}
else
{
start = 1 - target;
end = target;
}

sum = start;
printf("%d", start);
for (i = start + 1; i <= end; i++)
{
printf(" + %d", i);
sum += i;
}
printf(" = %d\n", sum);
}

int main()
{
consecutive( -7 );
consecutive( -1 );
consecutive( 0 );
consecutive( 1 );
consecutive( 7 );
consecutive( 296 );
return EXIT_SUCCESS;
}

It works far better than yours; no dynamic memory
management or any other such nuisances and answer is
always correct too. So why we should even eyeball
your solution?
j***@verizon.net
2017-03-10 15:16:51 UTC
Reply
Permalink
Raw Message
Post by Ike Naar
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.
To me, producing consecutive integers boils down to
for (i = start; i <= end; i++)
printf("%\n", i);
Sorry. I was in a bit of a rush.
I meant consecutive integers which add up to the target.
{1,2,3,4,5}
{4,5,6}
{7,8}
{15}
Your algorithm produces the set {1,2,3,4,5},
Joe's algorithm produces the set {15}.
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.
Ike Naar
2017-03-10 19:20:33 UTC
Reply
Permalink
Raw Message
Post by j***@verizon.net
{-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.
James Kuyper
2017-03-10 20:21:18 UTC
Reply
Permalink
Raw Message
Post by Ike Naar
Post by j***@verizon.net
{-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.
My point is that this is only an assumption on your part - it's one of
the many details he left unspecified.
Ike Naar
2017-03-10 20:36:19 UTC
Reply
Permalink
Raw Message
Post by James Kuyper
Post by Ike Naar
Post by j***@verizon.net
{-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.
My point is that this is only an assumption on your part - it's one of
the many details he left unspecified.
Correct.
insane_goat
2017-03-12 13:19:26 UTC
Reply
Permalink
Raw Message
Post by James Kuyper
Post by Ike Naar
Post by j***@verizon.net
{-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}
Post by James Kuyper
Post by Ike Naar
Post by j***@verizon.net
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.
My point is that this is only an assumption on your part - it's one of
the many details he left unspecified.
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.
--
Daniel Roskams
Kenny McCormack
2017-03-12 13:25:47 UTC
Reply
Permalink
Raw Message
In article <oa3hsu$mge$***@gioia.aioe.org>,
insane_goat <***@nothing.net> wrote:
...
Post by insane_goat
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 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.

It is an interesting theoretical question to consider how much time will
have gone by when these terms are similarly rendered non-acceptable/non-PC.
And, of course, it will be interesting to see what new terms will come into
usage as replacements.

Time alone will tell...
--
Kenny, I'll ask you to stop using quotes of mine as taglines.

- Rick C Hodgin -
Malcolm McLean
2017-03-12 15:11:23 UTC
Reply
Permalink
Raw Message
Post by Kenny McCormack
...
Post by insane_goat
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 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.
When I was at school, the lowest class was called "remedial". It was a
euphemism, but of course it didn't work, as most boys thought the word
meant "especially thick".
Kenny McCormack
2017-03-12 15:53:16 UTC
Reply
Permalink
Raw Message
Post by Malcolm McLean
Post by Kenny McCormack
...
Post by insane_goat
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 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.
When I was at school, the lowest class was called "remedial". It was a
euphemism, but of course it didn't work, as most boys thought the word
meant "especially thick".
I think something like half of all teaching effort in US colleges these
days is "remedial" - i.e., teaching people things they should have learned
in high school (or earlier).
--
"If God wanted us to believe in him, he'd exist."

(Linda Smith on "10 Funniest Londoners", TimeOut, 23rd June, 2005.)
Malcolm McLean
2017-03-12 17:50:43 UTC
Reply
Permalink
Raw Message
Post by Kenny McCormack
I think something like half of all teaching effort in US colleges these
days is "remedial" - i.e., teaching people things they should have learned
in high school (or earlier).
That's true in the UK too.

A lot of universities are quietly and competently teaching youngsters
things they should have learnt at school and didn't. It's something they
have to keep quiet about, and university education is far more expensive
that state school education, but the universities are selective, so
the bottom 50%, including the long tail of disruptive elements, are
eliminated. Then 18-21 year olds are in some ways easier to teach
than younger children because discipline problems present if different,
more manageable forms. Then, though it's dreadful to have to say this,
an assault on a member of university staff by a student is in the eyes
of the police an adult-to-adult matter, and dealt with as such. Consequently
such actions by students are rare.
Kenny McCormack
2017-03-12 18:25:51 UTC
Reply
Permalink
Raw Message
Post by Malcolm McLean
Post by Kenny McCormack
I think something like half of all teaching effort in US colleges these
days is "remedial" - i.e., teaching people things they should have learned
in high school (or earlier).
That's true in the UK too.
A lot of universities are quietly and competently teaching youngsters
things they should have learnt at school and didn't. It's something they
have to keep quiet about, and university education is far more expensive
that state school education, but the universities are selective, so the
bottom 50%, including the long tail of disruptive elements, are
eliminated. Then 18-21 year olds are in some ways easier to teach than
younger children because discipline problems present if different, more
manageable forms. Then, though it's dreadful to have to say this, an
assault on a member of university staff by a student is in the eyes of the
police an adult-to-adult matter, and dealt with as such. Consequently such
actions by students are rare.
Interesting stuff. I'm assuming:

1) That by 'present if different', you meant 'present in different'.

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.

(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.
--
The randomly chosen signature file that would have appeared here is more than 4
lines long. As such, it violates one or more Usenet RFCs. In order to remain
in compliance with said RFCs, the actual sig can be found at the following URL:
http://user.xmission.com/~gazelle/Sigs/God
Malcolm McLean
2017-03-12 23:20:00 UTC
Reply
Permalink
Raw Message
Post by Kenny McCormack
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.
Post by Kenny McCormack
2) That the UK has evolved the same "everybody goes to college"
? mindset as the US. Such that everybody assumes that if you
Post by Kenny McCormack
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.
Post by Kenny McCormack
(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.
Gordon Burditt
2017-03-14 06:09:50 UTC
Reply
Permalink
Raw Message
Post by Kenny McCormack
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.
Richard Bos
2017-03-14 07:43:40 UTC
Reply
Permalink
Raw Message
Post by Gordon Burditt
Post by Kenny McCormack
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.)
James R. Kuyper
2017-03-12 14:28:35 UTC
Reply
Permalink
Raw Message
On 03/12/2017 09:19 AM, insane_goat wrote:
...
Post by insane_goat
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.
Gareth Owen
2017-03-11 07:42:33 UTC
Reply
Permalink
Raw Message
Post by Ike Naar
Post by j***@verizon.net
{-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
Jens Thoms Toerring
2017-03-10 10:21:02 UTC
Reply
Permalink
Raw Message
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.
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 ___ ***@toerring.de
\__________________________ http://toerring.de
Nathan Wagner
2017-03-10 22:07:21 UTC
Reply
Permalink
Raw Message
Post by Jens Thoms Toerring
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
Nathan Wagner
2017-03-10 22:20:02 UTC
Reply
Permalink
Raw Message
Post by Nathan Wagner
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
jr
2017-03-11 07:49:24 UTC
Reply
Permalink
Raw Message
Post by Nathan Wagner
Looks good, must be perfect.
expcept for exact powers of two. :-)
Jens Thoms Toerring
2017-03-11 23:38:39 UTC
Reply
Permalink
Raw Message
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
Tim Rentsch
2017-04-17 04:18:41 UTC
Reply
Permalink
Raw Message
Post by Jens Thoms Toerring
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';-)
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;
}

Loading...