Displaying 1-10 of 26 results found.
Number of iterations of "take odd part of phi" ( A053575) to reach 1 from n.
+20
11
0, 1, 1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 2, 2, 1, 1, 1, 2, 3, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 1, 2, 1, 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, 1, 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
FORMULA
For n > 1, a(n) = a( A053575(n)) + 1.
EXAMPLE
a(18) = 2 because it takes two steps to reach 1 from 18: phi(18) = 6, the odd part of which is 3, and phi(3) = 2, the odd part of which is 1.
a(19) = 3 because it takes three steps to reach 1 from 19: phi(19) = 18, the odd part of which is 9, and phi(9) = 6, the odd part of which is 3, and phi(3) = 2, the odd part of which is 1.
MATHEMATICA
oddPhi[n_] := Module[{phi = EulerPhi[n]}, phi/2^IntegerExponent[phi, 2]]; Table[Length[NestWhileList[oddPhi[#] &, n, # > 1 &]] - 1, {n, 100}] (* T. D. Noe, Oct 07 2013 *)
PROG
(Haskell)
a227944 n = fst $
until ((== 1) . snd) (\(i, x) -> (i + 1, a053575 x)) (0, n)
Carmichael numbers k for which A053575(k) [the odd part of phi] divides k-1.
+20
11
561, 1105, 2465, 6601, 8911, 10585, 46657, 62745, 162401, 410041, 449065, 5148001, 5632705, 6313681, 6840001, 7207201, 11119105, 11921001, 19683001, 21584305, 26719701, 41298985, 55462177, 64774081, 67371265, 79411201, 83966401, 87318001, 99861985, 100427041, 172290241, 189941761, 484662529, 790623289, 809883361
COMMENTS
Lehmer conjectured that the equation k * phi(n) = n - 1 (with k integer) has no solutions for any composite n (i.e., when k > 1). If this sequence has no common terms with A339818, then the conjecture certainly holds.
MATHEMATICA
carmichaels = Cases[Import["https://oeis.org/ A002997/b002997.txt", "Table"], {_, _}][[;; , 2]]; oddPart[n_] := n/2^IntegerExponent[n, 2]; q[n_] := Divisible[n - 1, oddPart[EulerPhi[n]]]; Select[carmichaels, q] (* Amiram Eldar, Dec 26 2020 *)
PROG
(PARI)
isA339869(n) = ((n>1)&&!isprime(n)&&(!((n-1)% A002322(n)))&&!((n-1)% A000265(eulerphi(n))));
Odd composite numbers k such that A053575(k) [the odd part of phi] divides k-1.
+20
9
15, 51, 85, 91, 255, 435, 451, 561, 595, 771, 1105, 1261, 1285, 1351, 1695, 2091, 2431, 2465, 3655, 3855, 4369, 4795, 5083, 5151, 5383, 6601, 6643, 6735, 7051, 8245, 8481, 8695, 8911, 8995, 9061, 9605, 10585, 11155, 13107, 15051, 15211, 16405, 16705, 17733, 18721, 19669, 20451, 21845, 22359, 23001, 26335, 28645
PROG
(PARI)
isA339880(n) = (bitand(n, 1)&&(n>1)&&!isprime(n)&&!((n-1)% A000265(eulerphi(n))));
Numbers k for which k-1 is a multiple of A053575(k) [the odd part of phi(k)].
+20
5
1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 15, 16, 17, 19, 20, 23, 24, 28, 29, 30, 31, 32, 34, 37, 40, 41, 43, 47, 48, 51, 52, 53, 59, 60, 61, 64, 66, 67, 68, 70, 71, 73, 79, 80, 83, 85, 89, 91, 96, 97, 101, 102, 103, 107, 109, 112, 113, 120, 127, 128, 130, 131, 136, 137, 139, 149, 151, 157, 160, 163, 167, 170, 173, 176, 179
PROG
(PARI)
isA339879(n) = !((n-1)% A000265(eulerphi(n)));
Odd numbers k for which k-1 is a multiple of A053575(k) [the odd part of phi(k)].
+20
4
1, 3, 5, 7, 11, 13, 15, 17, 19, 23, 29, 31, 37, 41, 43, 47, 51, 53, 59, 61, 67, 71, 73, 79, 83, 85, 89, 91, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 255, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313
COMMENTS
Sequence A003961( A340076(i)), i = 1.., sorted into ascending order. In other words, this sequence consists of such odd numbers k that A064989(k) is in A340076.
PROG
(PARI)
isA340077(n) = ((n%2)&&!((n-1)% A000265(eulerphi(n)))); (PARI)
A064989(n) = { my(f=factor(n)); if((n>1 && f[1, 1]==2), f[1, 2] = 0); for (i=1, #f~, f[i, 1] = precprime(f[i, 1]-1)); factorback(f) };
Carmichael numbers k for which A053575(k) [the odd part of phi] does not divide k-1.
+20
3
1729, 2821, 15841, 29341, 41041, 52633, 63973, 75361, 101101, 115921, 126217, 172081, 188461, 252601, 278545, 294409, 314821, 334153, 340561, 399001, 488881, 512461, 530881, 552721, 656601, 658801, 670033, 748657, 825265, 838201, 852841, 997633, 1024651, 1033669, 1050985, 1082809, 1152271, 1193221, 1461241, 1569457
MATHEMATICA
odd[n_] := n/2^IntegerExponent[n, 2]; Select[Range[1, 10^6, 2], CompositeQ[#] && Divisible[# - 1, CarmichaelLambda[#]] && !Divisible[# - 1, odd @ EulerPhi[#]] &] (* Amiram Eldar, Dec 31 2020 *)
PROG
(PARI)
isA340092(n) = ((n>1)&&!isprime(n)&&(!((n-1)% A002322(n)))&&(0<((n-1)% A000265(eulerphi(n)))));
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).
Fully multiplicative with a(p) = A000265(p-1) for any prime p, where A000265(k) gives the odd part of k.
+10
30
1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 5, 1, 3, 3, 1, 1, 1, 1, 9, 1, 3, 5, 11, 1, 1, 3, 1, 3, 7, 1, 15, 1, 5, 1, 3, 1, 9, 9, 3, 1, 5, 3, 21, 5, 1, 11, 23, 1, 9, 1, 1, 3, 13, 1, 5, 3, 9, 7, 29, 1, 15, 15, 3, 1, 3, 5, 33, 1, 11, 3, 35, 1, 9, 9, 1, 9, 15, 3, 39, 1, 1, 5, 41, 3, 1, 21, 7, 5, 11, 1, 9, 11, 15, 23, 9, 1, 3, 9, 5, 1, 25, 1, 51, 3, 3
COMMENTS
For the comment here, we extend the definition of the second kind of Cunningham chain (see Wikipedia-article) so that also isolated primes for which neither (p+1)/2 nor 2p-1 is a prime are considered to be in singular chains, that is, in chains of the length one. If we replace one or more instances of any particular odd prime factor p in n with any odd prime q in such a chain, so that m = (q^k)*n / p^(e-k), where e is the exponent of p of n, and k <= e is the number of instances of p replaced with q, then it holds that a(m) = a(n), and by induction, the value stays invariant for any number of such replacements. Note also that A001222, but not necessarily A001221 will stay invariant in such changes. For example, if some of the odd prime divisors p of n are in A005382, then replacing it with 2p-1 (i.e., the corresponding terms of A005383), gives a new number m, for which a(m) = a(n). And vice versa, the same is true for any of the prime divisors > 3 of n that are in A005383, then replacing any one of them with (p+1)/2 will not affect the result. For example, a(37*37*37) = a(19*37*73) = 729 as 37 is both in A005382 and in A005383.
MATHEMATICA
Array[Times @@ Map[If[# <= 2, 1, (# - 1)/2^IntegerExponent[# - 1, 2]] &, Flatten[ConstantArray[#1, #2] & @@@ FactorInteger[#]]] &, 105] (* Michael De Vlieger, Jul 24 2020 *)
PROG
(PARI)
A336466(n) = { my(f=factor(n)); prod(k=1, #f~, A000265(f[k, 1]-1)^f[k, 2]); };
CROSSREFS
Cf. A000265, A003958, A005117, A005382, A005383, A053575, A329697, A333787, A335915, A336396, A336467, A336468, A339870, A339876 [= a( A122111(n))], A339903 [= a( A003961(n))], A340084 [= gcd(n-1, a(n))], A340085, A340086.
Dedekind psi function applied to the odd part of n: a(n) = A001615( A000265(n)).
+10
11
1, 1, 4, 1, 6, 4, 8, 1, 12, 6, 12, 4, 14, 8, 24, 1, 18, 12, 20, 6, 32, 12, 24, 4, 30, 14, 36, 8, 30, 24, 32, 1, 48, 18, 48, 12, 38, 20, 56, 6, 42, 32, 44, 12, 72, 24, 48, 4, 56, 30, 72, 14, 54, 36, 72, 8, 80, 30, 60, 24, 62, 32, 96, 1, 84, 48, 68, 18, 96, 48, 72, 12, 74, 38, 120, 20, 96, 56, 80, 6, 108, 42, 84, 32, 108
FORMULA
Multiplicative with a(2^e) = 1, a(p^e) = (p+1)*p^(e-1) for all odd primes p.
Sum_{k=1..n} a(k) ~ c * n^2, where c = 4/Pi^2 = 0.405284... ( A185199). - Amiram Eldar, Nov 19 2022 Dirichlet g.f.: (zeta(s)*zeta(s-1)/zeta(2*s))*(4^s-2^(s+1))/(4^s-1). - Amiram Eldar, Jan 04 2023
MATHEMATICA
f[p_, e_] := If[p == 2, 1, (p + 1)*p^(e - 1)]; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Aug 31 2021 *)
PROG
(PARI) A347385(n) = if(1==n, n, my(f=factor(n>>valuation(n, 2))); prod(i=1, #f~, f[i, 1]^f[i, 2] + f[i, 1]^(f[i, 2]-1)));
Exponent of 2 in phi(n) where phi(n) = A000010(n).
+10
9
0, 0, 1, 1, 2, 1, 1, 2, 1, 2, 1, 2, 2, 1, 3, 3, 4, 1, 1, 3, 2, 1, 1, 3, 2, 2, 1, 2, 2, 3, 1, 4, 2, 4, 3, 2, 2, 1, 3, 4, 3, 2, 1, 2, 3, 1, 1, 4, 1, 2, 5, 3, 2, 1, 3, 3, 2, 2, 1, 4, 2, 1, 2, 5, 4, 2, 1, 5, 2, 3, 1, 3, 3, 2, 3, 2, 2, 3, 1, 5, 1, 3, 1, 3, 6, 1, 3, 3, 3, 3, 3, 2, 2, 1, 3, 5, 5, 1, 2, 3, 2, 5, 1, 4, 4, 2, 1, 2, 2, 3, 3, 4, 4, 2, 3, 3, 3, 1, 5, 5
FORMULA
Additive with a(2^e) = e-1, and a(p^e) = A007814(p-1) for an odd prime p. - Amiram Eldar, Sep 05 2023
EXAMPLE
For n = 513 = 27*19, phi(513) = 4*81 so exponent of 2 is 2, thus a(513) = 2.
PROG
(PARI) vector(66, n, valuation(eulerphi(n), 2)) \\ Joerg Arndt, Apr 22 2011
Search completed in 0.014 seconds
|