Displaying 1-10 of 13 results found.
a(1) = 0, then after the first differences of A064415.
+20
5
0, 1, 0, 1, 0, 0, 0, 1, -1, 1, 0, 0, 0, 0, 0, 1, 0, -1, 0, 1, -1, 1, 0, 0, 0, 0, -1, 1, 0, 0, 0, 1, -1, 1, -1, 0, 0, 0, 0, 1, 0, -1, 0, 1, -1, 1, 0, 0, -1, 1, 0, 0, 0, -1, 1, 0, -1, 1, 0, 0, 0, 0, -1, 2, -1, 0, 0, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -2, 2, 0, -1, 1, -1, 0, 1, 0, -1, 0, 1, -1, 1, -1, 1, 0, -1, 0, 1, 0, 0, 0, 0, -1
PROG
(PARI)
A003434(n) = for(k=0, n, n>1 || return(k); n=eulerphi(n));
CROSSREFS
Also, from a(3) onward the first differences of A054725.
0, 0, 1, 0, 1, 1, 1, 0, 2, 1, 1, 1, 1, 1, 2, 0, 1, 2, 2, 1, 2, 1, 1, 1, 2, 1, 3, 1, 2, 2, 1, 0, 2, 1, 2, 2, 2, 2, 2, 1, 1, 2, 2, 1, 3, 1, 1, 1, 2, 2, 2, 1, 2, 3, 2, 1, 3, 2, 2, 2, 1, 1, 3, 0, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 3, 2, 2, 2, 2, 1, 4, 1, 1, 2, 2, 2, 3, 1, 2, 3, 2, 1, 2, 1, 3, 1, 1, 2, 3, 2, 2, 2, 1, 1, 3
FORMULA
a(2) = 0, a(p) = A334097(p+1)- A064415(p-1) for odd primes p, a(m*n) = a(m)+a(n), if m,n > 1. a(3^k) = k for all k>= 0.
PROG
(PARI)
A064415(n) = { my(f=factor(n)); sum(k=1, #f~, if(2==f[k, 1], f[k, 2], f[k, 2]* A064415(f[k, 1]-1))); };
A334097(n) = { my(f=factor(n)); sum(k=1, #f~, if(2==f[k, 1], f[k, 2], f[k, 2]* A334097(f[k, 1]+1))); };
\\ Or alternatively as:
A334862(n) = { my(f=factor(n)); sum(k=1, #f~, if(2==f[k, 1], 0, f[k, 2]*( A334097(f[k, 1]+1)- A064415(f[k, 1]-1)))); };
Number of integers q such that phiter(q)=n where phiter(n) = A064415(n).
+20
2
1, 2, 5, 11, 26, 59, 137, 312, 719, 1651, 3816, 8757, 20202, 46440, 106957, 245989, 566561, 1303968, 3002247, 6910122, 15909143
FORMULA
If 2<=n<=6, a(n)=a(n-1)+3*a(n-2).
AUTHOR
Christian WEINSBERG (cweinsbe(AT)fr.packardbell.org), Sep 30 2001
0, 1, 2, 6, 10, 14, 18, 27, 31, 40, 49, 58, 67, 76, 85, 101, 117, 126, 135, 151, 160, 176, 192, 208, 224, 240, 249, 265, 281, 297, 313, 338, 354, 379, 395, 411, 427, 443, 459, 484, 509, 525, 541, 566, 582, 607, 632, 657, 673, 698, 723, 748, 773, 789, 814, 839
Number of primes q such that phiter(q)=n where phiter(n)= A064415(n).
+20
1
0, 2, 2, 3, 6, 12, 23, 46, 94, 198, 424, 854, 1859, 3884, 8362, 17837, 38977, 84188, 183167, 398685, 874078
COMMENTS
For n>1, a(n) is the number of primes in class n of the Phi iteration. See A003434 and A058812. [From T. D. Noe, Nov 05 2008]
AUTHOR
Christian WEINSBERG (cweinsbe(AT)fr.packardbell.org), Oct 10 2001
a(n) is the number of iterations needed to reach a power of 2 starting at n and using the map k -> k-(k/p), where p is the largest prime factor of k.
+10
65
0, 0, 1, 0, 1, 1, 2, 0, 2, 1, 2, 1, 2, 2, 2, 0, 1, 2, 3, 1, 3, 2, 3, 1, 2, 2, 3, 2, 3, 2, 3, 0, 3, 1, 3, 2, 3, 3, 3, 1, 2, 3, 4, 2, 3, 3, 4, 1, 4, 2, 2, 2, 3, 3, 3, 2, 4, 3, 4, 2, 3, 3, 4, 0, 3, 3, 4, 1, 4, 3, 4, 2, 3, 3, 3, 3, 4, 3, 4, 1, 4, 2, 3, 3, 2, 4, 4, 2, 3, 3, 4, 3, 4, 4, 4, 1, 2, 4, 4, 2
COMMENTS
Also the least number of iterations of nondeterministic map k -> k-(k/p) needed to reach a power of 2, when any prime factor p of k can be used. The minimal length path to the nearest power of 2 (= 2^ A064415(n)) is realized whenever one uses any of the A005087(k) distinct odd prime factors of the current k, at any step of the process. For example, this could be done by iterating with the map k -> k-(k/ A078701(k)), i.e., by using the least odd prime factor of k (instead of the largest prime). Proof: Viewing the prime factorization of changing k as a multiset ("bag") of primes, we see that liquefying any odd prime p with step p -> (p-1) brings at least one more 2 to the bag, while applying p -> (p-1) to any 2 just removes it from the bag, but gives nothing back. Thus the largest (and thus also the nearest) power of 2 is reached by eliminating - step by step - all odd primes from the bag, but none of 2's, and it doesn't matter in which order this is done.
The above implies also that the sequence is totally additive, which also follows because both A064097 and A064415 are. That A064097(n) = A329697(n) + A054725(n) for all n > 1 can be also seen by comparing the initial conditions and the recursion formulas of these three sequences. For any n, A333787(n) is either the nearest power of 2 reached (= 2^ A064415(n)), or occurs on some of the paths from n to there. (End)
LINKS
Michael De Vlieger, Annotated fan style binary tree labeling the index n, with a color code where black represents a(n) = 0, red a(n) = 1, and magenta the largest value in a(n) for n = 1..16383.
FORMULA
a(1) = a(2) = 0; and for n > 2, a(p) = 1 + a(p-1) if p is an odd prime and a(n*m) = a(n) + a(m) if m,n > 1. [This is otherwise equal to the definition of A064097, except here we have a different initial condition, with a(2) = 0]. a(p) = 1+a(p-1), for all odd primes p.
If A209229(n) == 1 [when n is a power of 2], a(n) = 0, Equivalently, for non-powers of 2, a(n) = 1 + a(n-(n/ A078701(n))), or equivalently, for non-powers of 2, a(n) = 1 + Min a(n - n/p), for p prime and dividing n.
(End)
(End)
EXAMPLE
The trajectory of 15 is {12, 8}, taking 2 iterations to reach 8 = 2^3. So a(15) is 2.
Considering all possible paths from 15 to 1 nondeterministic map k -> k-(k/p), where p can be any prime factor of k, we obtain the following graph:
15
/ \
/ \
10 12
/ \ / \
/ \ / \
5 8 6
\__ | __/|
\_|_/ |
4 3
\ /
\ /
2
|
1.
It can be seen that there's also alternative route to 8 via 10 (with 10 = 15-(15/3), where 3 is not the largest prime factor of 15), but it's not any shorter than the route via 12.
(End)
MATHEMATICA
a[n_] := Length@ NestWhileList[# - #/FactorInteger[#][[-1, 1]] &, n, # != 2^IntegerExponent[#, 2] &] -1; Array[a, 100]
PROG
(PARI)
up_to = 2^24;
A329697list(up_to) = { my(v=vector(up_to)); v[1] = 0; for(n=2, up_to, v[n] = if(!bitand(n, n-1), 0, 1+vecmin(apply(p -> v[n-n/p], factor(n)[, 1]~)))); (v); };
v329697 = A329697list(up_to);
CROSSREFS
Cf. A000265, A003401, A005087, A052126, A053575, A054725, A064097, A064415, A078701, A087436, A147545, A171462, A209229, A333123, A333787, A333790, A334107, A334109, A335875, A334204, A335880, A335881, A336396, A336466, A336469 [= a(phi(n))], A336928 [= a(sigma(n))], A336470, A336477, A339970. Cf. A334099 (a right inverse, positions of the first occurrence of each n).
A quasi-logarithm defined inductively by a(1) = 0 and a(p) = 1 + a(p-1) if p is prime and a(n*m) = a(n) + a(m) if m,n > 1.
+10
48
0, 1, 2, 2, 3, 3, 4, 3, 4, 4, 5, 4, 5, 5, 5, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 6, 6, 7, 6, 7, 5, 7, 6, 7, 6, 7, 7, 7, 6, 7, 7, 8, 7, 7, 8, 9, 6, 8, 7, 7, 7, 8, 7, 8, 7, 8, 8, 9, 7, 8, 8, 8, 6, 8, 8, 9, 7, 9, 8, 9, 7, 8, 8, 8, 8, 9, 8, 9, 7, 8, 8, 9, 8, 8, 9, 9, 8, 9, 8, 9, 9, 9, 10, 9, 7, 8, 9, 9, 8, 9, 8, 9, 8
COMMENTS
Note that this is the logarithm of a completely multiplicative function. - Michael SomosNumber of iterations of r -> r - (largest divisor d < r) needed to reach 1 starting at r = n. a(n) = a(n - A032742(n)) + 1 for n >= 2. - Jaroslav Krizek, Jan 28 2010 Krizek's comment above stems from the fact that n - n/p = (p-1)*(n/p), where p is the least prime dividing n [= A020639(n), thus n/p = A032742(n)] and because this is fully additive sequence we can write a(n) = a(p) + a(n/p) = (1+a(p-1)) + a(n/p) = 1 + a((p-1)*(n/p)) = 1 + a(n - n/p), for any composite n. Note that in above formula p can be any prime factor of n, not only the smallest, which proves Robert G. Wilson v's comment in A333123 that all such iteration paths from n to 1 are of the same length, regardless of the route taken. (End)
Moreover, those paths form the chains of a graded poset, which is also a lattice. See the Mathematics Stack Exchange link.
Keeping the formula otherwise same, but changing it for primes either as a(p) = 1 + a( A064989(p)), a(p) = 1 + a(floor(p/2)) or a(p) = 1 + a( A048673(p)) gives sequences A056239, A064415 and A334200 respectively. (End)
a(n) is the number of iterations r-> A060681(r) to reach 1 starting at r=n. - R. J. Mathar, Nov 06 2023
FORMULA
Conjectures: for n>1, log(n) < a(n) < (5/2)*log(n); lim n ->infinity sum(k=1, n, a(k))/(n*log(n)-n) = C = 1.8(4)... - Benoit Cloitre, Oct 30 2002 Conjecture: for n>1, floor(log_2(n)) <= a(n) < (5/2)*log(n). - Robert G. Wilson v, Aug 10 2013 a(n) = Sum_{k=1..n} a(p_k)*e_k if n is composite with factorization p_1^e_1 * ... * p_k^e_k. - Orson R. L. Peters, May 10 2016
EXAMPLE
a(19) = 6: 19 - 1 = 18; 18 - 9 = 9; 9 - 3 = 6; 6 - 3 = 3; 3 - 1 = 2; 2 - 1 = 1. That is a total of 6 iterations. - Jaroslav Krizek, Jan 28 2010 We can follow also alternative routes, where we do not always select the largest proper divisor to subtract, for example, from 19 to 1, we could go as:
19-1 = 18; 18-(18/3) = 12; 12-(12/2) = 6; 6-(6/3) = 4; 4-(4/2) = 2; 2-(2/2) = 1, or as
19-1 = 18; 18-(18/3) = 12; 12-(12/3) = 8; 8-(8/2) = 4; 4-(4/2) = 2; 2-(2/2) = 1,
both of which also have exactly 6 iterations.
(End)
MAPLE
a:= proc(n) option remember;
add((1+a(i[1]-1))*i[2], i=ifactors(n)[2])
end:
# alternative which can be even used outside this entry
option remember ;
add((1+procname(i[1]-1))*i[2], i=ifactors(n)[2]) ;
end proc:
MATHEMATICA
quasiLog := (Length@NestWhileList[# - Divisors[#][[-2]] &, #, # > 1 &] - 1) &;
quasiLog /@ Range[1024]
fi[n_] := Flatten[ Table[#[[1]], {#[[2]]}] & /@ FactorInteger@ n]; a[1] = 0; a[n_] := If[ PrimeQ@ n, a[n - 1] + 1, Plus @@ (a@# & /@ fi@ n)]; Array[a, 105] (* Robert G. Wilson v, Jul 17 2013 *) a[n_] := Length@ NestWhileList[# - #/FactorInteger[#][[1, 1]] &, n, # != 1 &] - 1; Array[a, 100] (* or *)
a[n_] := a[n - n/FactorInteger[n][[1, 1]]] +1; a[1] = 0; Array[a, 100] (* Robert G. Wilson v, Mar 03 2020 *)
PROG
(PARI) NN=200; an=vector(NN);
a(n)=an[n];
for(n=2, NN, an[n]=if(isprime(n), 1+a(n-1), sumdiv(n, p, if(isprime(p), a(p)*valuation(n, p)))));
for(n=1, 100, print1(a(n)", "))
(PARI) a(n)=if(isprime(n), return(a(n-1)+1)); if(n==1, return(0)); my(f=factor(n)); apply(a, f[, 1])~ * f[, 2] \\ Charles R Greathouse IV, May 10 2016 (Haskell)
import Data.List (genericIndex)
a064097 n = genericIndex a064097_list (n-1)
a064097_list = 0 : f 2 where
f x | x == spf = 1 + a064097 (spf - 1) : f (x + 1)
| otherwise = a064097 spf + a064097 (x `div` spf) : f (x + 1)
where spf = a020639 x
(Scheme)
CROSSREFS
Similar to A061373 which uses the same recurrence relation but a(1) = 1. Cf. A003313, A005245, A020639, A032742, A052126, A054725, A060681, A064415, A073933, A076142, A076091, A175125, A256653, A307742, A323076, A323077, A329697, A333123, A334200, A334202, A334203, and array A334111. Cf. A000079 (position of last occurrence), A105017 (position of records), A334197 (positions of record jumps upward).
AUTHOR
Thomas Schulze (jazariel(AT)tiscalenet.it), Sep 16 2001
a(n) = A329697(phi(n)), where A329697 is totally additive with a(2) = 0 and a(p) = 1 + a(p-1) for odd primes.
+10
10
0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 2, 0, 1, 1, 2, 0, 1, 1, 2, 1, 2, 0, 2, 0, 1, 0, 1, 1, 2, 2, 1, 0, 1, 1, 3, 1, 1, 2, 3, 0, 3, 1, 0, 1, 2, 2, 1, 1, 2, 2, 3, 0, 2, 2, 2, 0, 1, 1, 3, 0, 2, 1, 3, 1, 2, 2, 1, 2, 2, 1, 3, 0, 3, 1, 2, 1, 0, 3, 2, 1, 2, 1, 2, 2, 2, 3, 2, 0, 1, 3, 2, 1, 2, 0, 2, 1, 1
FORMULA
Additive with a(2^e) = 0, and for odd primes p, a(p^e) = A329697((p - 1)*p^(e-1)) = e* A329697(p) - 1.
MATHEMATICA
Array[Length@ NestWhileList[# - #/FactorInteger[#][[-1, 1]] &, EulerPhi[#], # != 2^IntegerExponent[#, 2] &] - 1 &, 105] (* Michael De Vlieger, Jul 24 2020 *)
PROG
(PARI)
A329697(n) = if(!bitand(n, n-1), 0, 1+ A329697(n-(n/vecmax(factor(n)[, 1]))));
\\ Or alternatively as:
A336469(n) = { my(f = factor(n)); sum(k=1, #f~, if(2==f[k, 1], 0, -1 + (f[k, 2]* A329697(f[k, 1])))); };
a(n) is the number of iterations of the Euler phi function needed to reach a power of 2, when starting from n.
+10
7
0, 0, 1, 0, 1, 1, 2, 0, 2, 1, 2, 1, 2, 2, 1, 0, 1, 2, 3, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 1, 2, 0, 2, 1, 2, 2, 3, 3, 2, 1, 2, 2, 3, 2, 2, 3, 4, 1, 3, 2, 1, 2, 3, 3, 2, 2, 3, 3, 4, 1, 2, 2, 3, 0, 2, 2, 3, 1, 3, 2, 3, 2, 3, 3, 2, 3, 2, 2, 3, 1, 4, 2, 3, 2, 1, 3, 3, 2, 3, 2, 3, 3, 2, 4, 3, 1, 2, 3, 2, 2, 3, 1, 2, 2, 2
FORMULA
The smallest x so that Nest[ EulerPhi, n, x ] = 2^w is just achieved.
(End)
EXAMPLE
If n is a power of 2, then a(n)=0 by definition. If n = 59049, then by iterating with phi, we get 59049 -> 39366 -> 13122 -> 4374 -> 1458 -> 486 -> 162 -> 54 -> 18 -> 6 -> 2 -> 1. It took ten steps to reach the first power of 2 (2 in this case), so a(59049) = 10.
MATHEMATICA
Table[If[IntegerQ@ Log2@ n, 0, -1 + Length@ NestWhileList[EulerPhi, n, ! IntegerQ@ Log2@ # &]], {n, 105}] (* Michael De Vlieger, Aug 01 2017 *)
EXTENSIONS
Definition corrected and simplified, example corrected by Antti Karttunen, Aug 28 2021
a(n) is the number of iterations of the Euler totient function to reach 1, starting at n!.
+10
7
0, 1, 2, 4, 6, 8, 10, 13, 15, 18, 21, 24, 27, 30, 33, 37, 41, 44, 47, 51, 54, 58, 62, 66, 70, 74, 77, 81, 85, 89, 93, 98, 102, 107, 111, 115, 119, 123, 127, 132, 137, 141, 145, 150, 154, 159, 164, 169, 173, 178, 183, 188, 193, 197, 202, 207, 211, 216, 221, 226, 231
COMMENTS
Powers of 2 arise at the end of iteration chains without interruption. Analogous to A053025 and A053034. The order of speed of convergence is as follows: A000005 > A000010 > A051953: e.g., for 20! the lengths of the corresponding iteration chains are 6, 51, and 101, respectively.
EXAMPLE
For n=1, no iteration is needed, so a(1)=0;
for n=2, the initial value is 2! = 2, so phi() must be applied once, thus a(2)=1;
for n=8, the iteration chain is {40320, 9216, 3072, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1}; its length = 14 = a(8) + 1, so the number of iterations applied to reach 1 is a(8)=13.
MATHEMATICA
Table[Length@ NestWhileList[EulerPhi, n!, # > 1 &] - 1, {n, 61}] (* or *)
Table[Length@ FixedPointList[EulerPhi, n!] - 2, {n, 61}] (* Michael De Vlieger, Jan 01 2017 *)
PROG
(PARI) a(n) = {my(nb = 0, ns = n!); while (ns != 1, ns = eulerphi(ns); nb++); nb; } \\ Michel Marcus, Jan 01 2017
Search completed in 0.011 seconds
|