pd.if.org Git - scripts/blob - conseqpart.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <math.h>
   4
   5 /*
   6  * observations:
   7  *
   8  * solutions of any length L starting at b have the sum
   9  * S = L * (L-1 + 2b ) / 2
  10  *
  11  * This sum must equal the target t, so the base for a given length is
  12  * t = L * (L-1+2b) / 2
  13  * b = (2t/L-L+1)/2
  14  *
  15  * Since b must be an integer, t % ( (L+1)*L / 2 ) must equal 0
  16  * 2t % L must be zero and
  17  * 2t/L - L + 1 must be even
  18  *
  19  * With a minimum base of 1, the sum is (L+1)*L / 2,
  20  * which must not exceed the target
  21  * t >= (L+1)*L/2
  22  * L <= (sqrt(8t+1)-1) / 2
  23  *
  24  * Even targets must have solution lengths >= 3
  25  * even length solutions can start on any number
  26  * odd length solutions must be centered on an even number
  27  *
  28  * Odd targets must have an odd number of odd numbers
  29  * in the solution
  30  * they always have an even length solution of t/2 + t/2 + 1
  31  *
  32  */
  33 int main(int ac, char *av[]) {
  34         unsigned target; /* number to decompose */
  35         unsigned sbase; /* lowest number in solution */
  36         unsigned slen; /*  N quantity of numbers in solution */
  37         int oddtarget;
  38         unsigned maxlen;
  39
  40         target = atoi(av[1]);
  41
  42         maxlen = (sqrt(8.0*target+1.0)-1) / 2;
  43         oddtarget = target % 2;
  44
  45         if (oddtarget) {
  46                 printf("2 %d .. %d\n", target/2, target/2+1);
  47         }
  48
  49         for (slen=3; slen <= maxlen; slen++) {
  50                 if (oddtarget && (slen % 2 == 0 && (slen/2 % 2 == 0))) {
  51                         continue;
  52                 }
  53
  54                 if (2 * target % slen != 0) {
  55                         continue;
  56                 }
  57                 if ( (2 * target / slen - slen + 1) % 2 != 0) {
  58                         continue;
  59                 }
  60
  61                 sbase = (2 * target / slen - slen + 1) / 2;
  62
  63                 printf("%d %d .. %d\n", slen, sbase, sbase+slen-1);
  64         }
  65
  66         return 0;
  67 }