%I #15 Jul 15 2017 11:26:08
%S 1,2,1,3,4,2,1,5,8,4,2,1,6,3,7,10,5,8,4,2,1,8,4,2,1,9,10,5,8,4,2,1,10,
%T 5,8,4,2,1,11,14,7,10,5,8,4,2,1,12,6,3,13,16,8,4,2,1,14,7,10,5,8,4,2,
%U 1,15,16,8,4,2,1,16,8,4,2,1,17,20,10,5,8,4,2,1,18,9,10,5,8,4,2,1,19,22,11,14
%N Triangle read by rows in which row n begins with n (n=1,2,3,...) and iterates the process of dividing n by 2 if n is even, adding 3 if n is an odd prime, otherwise adding 1; stopping when either 1 or 3 is reached.
%C The number of steps to reach 1 or 3 is in A081879.
%C The sequence is well-defined: iteration of f (the map defining the sequence) terminates either at 1 or 3 for all values of n>0. Proof: Assuming that all natural numbers < k converge, then if k is even it converges (as f(k)=k/2 < k) and if it is odd, then f(f(k)) is either (k+1)/2 or (k+3)/2 and these are less than k for all k>4.
%e Triangle begins:
%e 1;
%e 2,1;
%e 3;
%e 4,2,1;
%e 5,8,4,2,1;
%e 6,3;
%e 7,10,5,8,4,2,1;
%e ...
%o (PARI) xnprp3(n) = { for(x=1,n, p1 = x; print1(x" "); while(p1>1, if(p1%2==0,p1/=2, if(isprime(p1),p1+=3,p1 = p1+1;)); print1(p1" "); if(p1==3,break) ) ) }
%o (MIT Scheme) (define (isprime? n) (cond ((< n 4) (> n 1)) (else (let loop ((i (floor->exact (/ n 2)))) (cond ((= 1 i) #t) ((zero? (modulo n i)) #f) (else (loop (-1+ i))))))))
%o (define (A081878 upto-n) (let outloop ((x 1) (a (list))) (cond ((> x upto-n) (reverse! a)) (else (let inloop ((a (cons x a))) (let ((n (car a))) (cond ((and (not (= 1 n)) (not (= 3 n))) (cond ((even? n) (inloop (cons (/ n 2) a))) ((isprime? n) (inloop (cons (+ n 3) a))) (else (inloop (cons (1+ n) a))))) (else (outloop (1+ x) a)))))))))
%Y Cf. A081879.
%K easy,nonn,tabf
%O 1,2
%A _Cino Hilliard_, Apr 12 2003
%E Edited by _Antti Karttunen_ and _Jud McCranie_, Jun 03 2003
|