Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #105767
| Newsgroups | comp.lang.c |
|---|---|
| From | Nathan Wagner <nw@hydaspes.if.org> |
| Subject | Re: Program to find consecutive integers |
| References | <o9t9jl$bkg$1@gioia.aioe.org> <1bpohpg0sy.fsf@pfeifferfamily.net> <o9ti7j$lnp$1@gioia.aioe.org> <eifd0cF8evcU1@mid.uni-berlin.de> |
| Message-ID | <slrnoc68sp.688.nw@granicus.if.org> (permalink) |
| Date | 2017-03-10 22:07 +0000 |
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
Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll 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