import java.math.BigInteger;
import java.util.Arrays;  

public class BigIntegerDivisions {
	public static int[] tableau = new int[20];  


    public static int maxDivisionsBy2(BigInteger n) {
        int count = 0;
        while (n.mod(BigInteger.TWO).equals(BigInteger.ZERO) && !n.equals(BigInteger.ZERO)) {
            n = n.divide(BigInteger.TWO);
            count++;
        }
        return count;
    }
    
    public static BigInteger call(BigInteger val) { // val = 2^p * n - 1
        BigInteger one = BigInteger.ONE;
        BigInteger three = new BigInteger("3"); 
		
        int p = maxDivisionsBy2(val.add(one));
	    BigInteger n = (val.add(one)).divide(BigInteger.TWO.pow(p));
        BigInteger val2 = (three.pow(p).multiply(n)).subtract(one); // val2 = 3^p * n - 1
        int q = maxDivisionsBy2(val2);
	    BigInteger n3 = val2.divide(BigInteger.TWO.pow(q)); // n3 = (3^p * n - 1) / 2^q2

        return n3;
    }
 
public static BigInteger jump1(BigInteger val) {
	return val;
}

public static BigInteger jump2(BigInteger u) {
    if (u.compareTo(BigInteger.ONE) <= 0) return BigInteger.ONE;
    BigInteger v = u.divide(BigInteger.valueOf(5));
    if (v.signum() <= 0) v = BigInteger.ONE;
    if (!v.testBit(0)) v = v.add(BigInteger.ONE); // force impair
    return v;
}
public static BigInteger jump3(BigInteger u) {
    if (u.compareTo(BigInteger.ONE) <= 0) return BigInteger.ONE;
    BigInteger v = u.subtract(BigInteger.TWO);
    if (v.signum() <= 0) v = BigInteger.ONE;
    if (!v.testBit(0)) v = v.add(BigInteger.ONE); // force impair
    return v;
}
 

  
public static void parcourirImpairs(int choix ,BigInteger un) {
    BigInteger tmp;
    BigInteger premierePhase = null; 
int nbpas=0;	// première phase expansive détectée

    while (!un.equals(BigInteger.ONE)) {
        tmp = call(un);
		nbpas++;
        if (tmp.compareTo(un) > 0) {
            if (premierePhase == null) {
                // Première phase expansive trouvée
                premierePhase = tmp;
			
            } else {
                // Deuxième phase expansive trouvée : on mesure la quantité d'impairs entre les deux
                BigInteger amplitude = tmp.subtract(premierePhase).abs().divide(BigInteger.TWO);
                System.out.println(amplitude+"  qt d'impairs = "+nbpas);
                // Nouvelle référence
                premierePhase = tmp;
				nbpas=0;
            }
        }
		switch ( choix ) 
		{
			case 1 :
				un = jump1(tmp);
				 break;
			case 2 :
				un = jump2(tmp);
				 break;

			case 3 :
				un = jump3(tmp);
				 break;
			default :
				un=BigInteger.ONE;
				throw new IllegalArgumentException("tu as merder : " + choix);
		}
 
    if (premierePhase == null) {
        System.out.println("Aucune phase expansive détectée pour cette valeur initiale.");
    }
  }
}




public static void parcourirImpairsEtCompter(BigInteger un) {


	int i=0;
 
    long compteur = 0L;

 while (i<1001) { 
        BigInteger tmp = call(un);                  // une seule fois
        boolean expansif = tmp.compareTo(un) > 0;  // test expansif

        if (expansif) {
                 System.out.print(compteur+" ");
                compteur = 0L;
				if(i%50==0)System.out.println();
				i++;
        } else {
                 compteur++; 
       }
        un=un.subtract(BigInteger.TWO);
		if (un.compareTo(BigInteger.ONE) < 0) throw new IllegalArgumentException("tu as merder : " );
	}
	System.out.println();

    
}









	
    public static void main(String[] args) {
		//BigInteger n0=new   BigInteger("136516541451418438111828142512421421421452145214521452145214517316546246468411668167146176746646464654646662565418817981787154646454541873871387861768718718717378781781742873132131544869407");
		//n0=n0.pow(100);
		//if(!n0.testBit(0)){n0=n0.subtract(BigInteger.ONE);}
		BigInteger n0=new   BigInteger("131651651651651541616465161564654615654284684681884135");

		System.out.println("************** forme récursive ou compresser ************");
		parcourirImpairs(1,n0);
		System.out.println("************** forme récursive +  u_n/5 ******************");
		parcourirImpairs(2,n0);
		System.out.println("************** forme récursive +  u_n-2 ******************");
		parcourirImpairs(3,n0);
		System.out.println("************** parcours impair consecutif n0 ************");
		parcourirImpairsEtCompter(n0);
		n0=n0.pow(200);
		System.out.println("************** parcours impair consecutif n0^200 ********");
		parcourirImpairsEtCompter(n0);
		 
    }
}