/* los.c
 * 
 * Différences entre les nombres de Los Alamos (suite d'Ulam)
 * valeurs manquantes
 * écarts entre celles-ci : 1 2 3 5
 * vérif. des valeurs données par C. A. Pickover et calculées
 * par Clifford A. Pickover & Ken Shirriff
 * (d'après la traduction française de Wonders of numbers)
 * 
 * écrit en Nov. 2005 Jean-Paul Davalan <jpdvl@wanadoo.fr>
 * 
 * compilation :
 *                gcc -O2 -o los los.c
 * usage :
 *                los maxi u0 u1
 *                
 * exemple :
 *                los 300 1 2
 * résultats :
 *            1 4            différence 1 observée 4  fois
 *            2 13                      2          13
 *            3 8
 *            4 2
 *            5 7
 *            7 5
 *            8 4
 *            9 3
 *            10 3
 *            12 1
 *            13 1
 *            15 1
 *            20 1                  
 *            # Nbre 54        (nombre d'éléments calculés de la suite d'Ulam)
 *            # Nbre gaps 13   (nb d'élémts dans la colonne de gauche)
 *            # Gap maxi 20 20 (pour vérification !)
 *            # Gaps manquants 6 11 14 16 17 18 19 (dans la colonne de gauche)
 *
 *            1 2 3 5     (11-6=5, 14-11=3, 16-14=2, 17-16=1 )
 *            
 * le format de l'affichage permet l'utilisation de gnuplot sur le fichier :
 * les trois lignes suivantes dans une xterm (ou une konsole de Kde) permettent
 * de construire l'image png de la page
 * 
 *           los 50000 1 2 >l50000.g; \
 *           echo 'set term png size 350,250; set output "l50000.png"; \
 *           set logscale y 10;plot "l50000.g" w impulses;'|gnuplot
 *           
 * si vous aimez 'dumb' 
 *           los 50000 1 2 >l50000.g;echo 'set term dumb 55 20;set logscale y 10; \
 *           plot "l50000.g" w impulses;'|gnuplot
 *           
 * vous donne l'image Ascii suivante   (échelle logarithmique sur Oy)
 * 
  10000 ++----+------+-----+-----+-----+------+----++
        +     +      +     +     +"l50000.g" ****** +
        +                                           +
        +*                                          +
   1000 +*                                         ++
        +*                                          +
        +*   **                                     +
        +*  *****                                   +
    100 +** *****    *                             ++
        +** *****   **                              +
        +********* *****  *                         +
        +********* *****  *                         +
     10 +********* ****** * * *                    ++
        +********* ****** *****  *                  +
        ********** ****** *****  * *   *            +
        ********** ****** *****  ***   *      *     +
      1 *****************-******-***---*--*---*--***+
        0     20     40    60    80   100    120   140

        abscisses : Valeurs des Différences
        ordonnées :  nombres de fois (effectifs)
 */

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

int MAXI=1000000, MAXGAP=100000, MAXOUBLI=100000;

char *tab;
int *gap, ngap;
int *oubli, noubli, *doubli;
int a, b, n;
int diff=1, aff=0;

int main(int argc, char *argv[]) {
	int i=0, u, v,somme,curr,deb,total, der, maxg0=0, maxg, nbgaps=0, m, j;
	if(argc<3) return 0;
	if(argc==4) {
		MAXI=atoi(argv[1]);
		i=1;
	}
	a = atoi(argv[1+i]);
	b = atoi(argv[2+i]);
	
	tab = (char *)malloc(MAXI*sizeof(char));
	gap = (int *)malloc(MAXGAP*sizeof(int));
	oubli = (int *)malloc(MAXOUBLI*sizeof(int));
	doubli = (int *)malloc(MAXOUBLI*sizeof(int));
	for(i=0;i<MAXI;i++) tab[i] = (char)0;
	tab[a]=(char)1;
	tab[b]=(char)1;
	if (a>b){ 
		int c=b; b=a; a=c;
	}
	if(a==b) return 1;
	if(diff) {
	 if(aff) printf("%d ",b-a);
	 gap[b-a]=1;
	 maxg0 = b-a;
	 der = b;
	} else {
	  if(aff) printf("%d %d ",a,b); 
	}
	fflush(stdout);
	deb++;
	total=2;
	for(curr=deb; curr<MAXI; curr++) {
		somme=0;
		u=1;
		v=curr-1;
		while(u<v && somme<2) {
			if(tab[u]==1 && tab[v]==1) somme++;
			u++;
			v--;
		}
		if(somme==1) {
			if(diff) {
			    int d= curr-der;
			    if(aff) printf("%d ",d);
			    if(d>maxg0) maxg0=d;
			    if(d<MAXGAP) gap[d]++;
			    der=curr;
			} else {
			     if(aff) printf("%d ",curr);
			}
			if(aff) fflush(stdout);
			tab[curr]=(char)1;
			total++;
		}
	}
	printf("\n");
	if(diff) {
	for(i=1;i<MAXGAP;i++)
		if(gap[i]!=0) { 
			maxg=i;
			nbgaps++;
			printf("%d %d\n",i,gap[i]);
		}
	}
	printf("# Nbre %d\n",total);
	printf("# Nbre gaps %d\n", nbgaps);
	printf("# Gap maxi %d %d\n", maxg0, maxg);
	printf("# Gaps manquants ");
	noubli=0;
	for(i=1;i<maxg;i++) {
		if(gap[i]==0) {
			printf("%d ",i);
			oubli[noubli] = i;
			noubli++;
		}
	}
	printf("\n\n# ");
	for(j=1;j<noubli;j++) {
		m = oubli[j]-oubli[j-1];
		doubli[m]++;
	}
	for(j=0;j<MAXOUBLI;j++) {
		if(doubli[j]!=0) printf("%d ",j);
	}
	printf("\n");
	
	free(tab);
	free(gap);
	return 0;
}