Shrimp Factored Problem

Spesso per studiare un problema si cerca di semplificarlo con un altro, a volte l'espediente riesce ma in altri casi nasce un altro problema.

Un problema "carino" da me inventato mentre studiavo il problema di Collatz e gli automi cellulari è quello che
chiamo lo "Shrimp Factored Problem" ovvero il "problema del Gambero fattorizzato".

Il suo enunciato è il seguente:
Sia dato un intero N qualsiasi e si procede nel seguente modo:
1) Se N è primo si moltiplica randomicamente per un numero presente nell'intervallo [2,N-1] e si passa allo step successivo 2). Se N non è primo si prosegue lo stesso allo step 2).
2) Si fattorizza il numero N ottenuto dallo step 1) e si preleva il minor fattore. Se il fattore è 2 si arresta il procedimento, altrimenti si passa allo step 1) con l'N ottenuto

I quesiti che si pongono sono almeno due:
a) L'automa si arresta sempre? Ovvero la sequenza di numeri che si ottiene arriva sempre a 2? La sequenza è sempre convergente o può avere cicli?

b) Come si calcola il numero di step che verranno fatti?

Eccovi un algoritmo in PARI/GP utile all'analisi:

Shrimp(N)= local(s="", Np=0); {
 if( N == 2, error("You must insert N > 2"));
 s=concat(s,N);
 s=concat(s,",");
 i=1;
 while( N != 2,
        i++;
        A=factor(N);
        if(length(A)>=2 & A[1,1] != 2,
           c=random(N-1);
           if( c < 2, c=2;);
           print(c);
           N=A[1,1]*c;
           if( N > Np,
             Np = N;
             pos = i;
           );          
           s=concat(s,N);
           s=concat(s,",");
        );
        if( A[1,1] == 2,
            N = A[1,1];
            s=concat(s,N);
        );
 );
 r = pos/i * 1.0;
 print("Max = ", Np);
 print("r   = ", r*100);
 print(s);
 return;
}
Alcuni risultati:

? Shrimp(23)
23,207,492,2

? Shrimp(27)
27,63,168,2

? Shrimp(31)
31,837,192,2

? Shrimp(313)
313,35369,2581824,2

? Shrimp(723421)
723421,248066124847,1068167619936,2

? Shrimp(723421345678)
723421345678,2

Apparentemente si ferma subito.
Eccovi un altro esempio col 31, lanciato almeno due-tre volte (cambia il c randomico che faccio stampare prima di mostrare la sequenza numerica):
? Shrimp(31)
19
273
2357
451
1051
1225
1963
4365
11029
1657
211
396
31,589,5187,7071,1353,3153,3675,5889,13095,33087,4971,633,1188,2
? Shrimp(31)
11
128
31,341,1408,2
? Shrimp(31)
27
206
31,837,618,2

Anche qui apparentemente sembra esistere una "congettura del Massimo dello Shrimp Factored": il massimo si presenta sempre con una posizione non inferiore al 66,67%. Invece il contro-esempio:

 ? Shrimp(511)
493
105
396
Max = 3451
r   = 40.00000000000000000000000000
511,3451,735,1188,2

Si può avere meno del 40%?

Se avete una dimostrazione ai vari quesiti, fatemi sapere.

Alla prox