A334107 -id:A334107 - cp's OEIS frontend

A329697 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.

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

Offset: 1

Ali Sada and Robert G. Wilson v, Feb 28 2020

From Antti Karttunen, Apr 07 2020: (Start)
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)
A003401 gives the numbers k where a(k) = A005087(k). See also A336477. - Antti Karttunen, Mar 16 2021

			The trajectory of 15 is {12, 8}, taking 2 iterations to reach 8 = 2^3. So a(15) is 2.
From _Antti Karttunen_, Apr 07 2020: (Start)
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)

Antti Karttunen, Table of n, a(n) for n = 1..65537
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.

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. A000079, A334101, A334102, A334103, A334104, A334105, A334106 for positions of 0 .. 6 in this sequence, and also array A334100.
Cf. A334099 (a right inverse, positions of the first occurrence of each n).
Cf. A334091 (first differences), A335429 (partial sums).
Cf. also A331410 (analogous sequence when using the map k -> k + k/p), A334861, A335877 (their sums and differences), see also A335878 and A335884, A335885.

a[n_] := Length@ NestWhileList[# - #/FactorInteger[#][[-1, 1]] &, n, # != 2^IntegerExponent[#, 2] &] -1; Array[a, 100]

A329697(n) = if(!bitand(n,n-1),0,1+A329697(n-(n/vecmax(factor(n)[, 1])))); \\ Antti Karttunen, Apr 07 2020

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);
A329697(n) = v329697[n]; \\ Antti Karttunen, Apr 07 2020

A329697(n) = if(n<=2,0, if(isprime(n), A329697(n-1)+1, my(f=factor(n)); (apply(A329697, f[, 1])~ * f[, 2]))); \\ Antti Karttunen, Apr 19 2020

From Antti Karttunen, Apr 07-19 2020: (Start)
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(2n) = a(A000265(n)) = a(n).
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,
  otherwise a(n) = 1 + a(n-A052126(n)) = 1 + a(A171462(n)).
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.
a(n) = A064097(n) - A064415(n), or equally, a(n) = A064097(n) - A054725(n), for n > 1.
a(A019434(n)) = 1, a(A334092(n)) = 2, a(A334093(n)) = 3, etc. for all applicable n.
For all n >= 0, a(A334099(n)) = a(A000244(n)) = a(A000351(n)) = a(A001026(n)) = a(257^n) = a(65537^n) = n.
a(A122111(n)) = A334107(n), a(A225546(n)) = A334109(n).
(End)
From Antti Karttunen, Mar 16 2021: (Start)
a(n) = a(A336466(n)) + A087436(n) = A336396(n) + A087436(n).
a(A053575(n)) = A336469(n) = a(n) - A005087(n).
a(A147545(n)) = A000120(A147545(n)) - 1.
(End)

A334201 a(n) = A056239(n) - A061395(n).

Original entry on oeis.org

0, 0, 0, 1, 0, 1, 0, 2, 2, 1, 0, 2, 0, 1, 2, 3, 0, 3, 0, 2, 2, 1, 0, 3, 3, 1, 4, 2, 0, 3, 0, 4, 2, 1, 3, 4, 0, 1, 2, 3, 0, 3, 0, 2, 4, 1, 0, 4, 4, 4, 2, 2, 0, 5, 3, 3, 2, 1, 0, 4, 0, 1, 4, 5, 3, 3, 0, 2, 2, 4, 0, 5, 0, 1, 5, 2, 4, 3, 0, 4, 6, 1, 0, 4, 3, 1, 2, 3, 0, 5, 4, 2, 2, 1, 3, 5, 0, 5, 4, 5, 0, 3, 0, 3, 5

Offset: 1

Antti Karttunen, May 11 2020

nonn

a(n) is the sum of all other parts of the partition having Heinz number n except one instance of the largest part.

Antti Karttunen, Table of n, a(n) for n = 1..65537
Index entries for sequences computed from indices in prime factorization

Cf. A001222, A052126, A056239, A061395, A122111, A318995.
Sum of A339895 and A339896.
Differs from A323077 for the first time at n=169, where a(169) = 6, while A323077(169) = 5.
Cf. also A334107.

Array[Total[# /. {p_, c_} /; p > 0 :> PrimePi[p] c] - PrimePi@ #[[-1, 1]] &@ FactorInteger[#] &, 105] (* Michael De Vlieger, May 14 2020 *)

A064989(n) = {my(f); 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)};
A334201(n) = if(1==n,0,(bigomega(n)-1)+A334201(A064989(n)));

a(n) = A056239(n) - A061395(n) = A056239(A052126(n)).
a(n) = A318995(A122111(n)).
a(n) = a(A064989(n)) + A001222(n) - 1.
a(n) = A339895(n) + A339896(n). - Antti Karttunen, Dec 31 2020

A346700 Sum of the even bisection (even-indexed parts) of the integer partition with Heinz number n.

Original entry on oeis.org

0, 0, 0, 1, 0, 1, 0, 1, 2, 1, 0, 1, 0, 1, 2, 2, 0, 2, 0, 1, 2, 1, 0, 2, 3, 1, 2, 1, 0, 2, 0, 2, 2, 1, 3, 3, 0, 1, 2, 2, 0, 2, 0, 1, 2, 1, 0, 2, 4, 3, 2, 1, 0, 3, 3, 2, 2, 1, 0, 3, 0, 1, 2, 3, 3, 2, 0, 1, 2, 3, 0, 3, 0, 1, 3, 1, 4, 2, 0, 2, 4, 1, 0, 3, 3, 1, 2, 2, 0, 3, 4, 1, 2, 1, 3, 3, 0, 4, 2, 4, 0, 2, 0, 2, 3

Offset: 1

Gus Wiseman, Aug 03 2021

nonn

First differs from A334107 at a(64) = 3, A334107(64) = 2.

The Heinz number of a partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k). This gives a bijective correspondence between positive integers and integer partitions.

			The partition with Heinz number 1100 is (5,3,3,1,1), so a(1100) = 3 + 1 = 4.
The partition with Heinz number 2100 is (4,3,3,2,1,1), so a(2100) = 3 + 2 + 1 = 6.

Antti Karttunen, Table of n, a(n) for n = 1..10201
Antti Karttunen, Data supplement: n, a(n) computed for n = 1..65537
Index entries for sequences related to Heinz numbers

Sum of prime indices of A329888(n).
Subtracting from the odd version gives A344616 (non-reverse: A316524).
The unreversed version for standard compositions is A346633.
The odd non-reverse version is A346697.
The non-reverse version (multisets instead of partitions) is A346698.
The odd version is A346699.
A001414 adds up prime factors, row sums of A027746.
A056239 adds up prime indices, row sums of A112798.
A103919 counts partitions by sum and alternating sum (reverse: A344612).
A325534 counts separable partitions, ranked by A335433.
A325535 counts inseparable partitions, ranked by A335448.
A344606 counts alternating permutations of prime indices.
Cf. A000070, A025047, A124754, A209281, A329888, A341446, A344617, A344653, A345957, A345958, A346701, A346702, A346704.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Table[Total[Last/@Partition[Reverse[primeMS[n]],2]],{n,100}]

A346700(n) = if(1==n,0,my(f=factor(n),s=0,p=0); forstep(k=#f~,1,-1,while(f[k,2], s += (p%2)*primepi(f[k,1]); f[k,2]--; p++)); (s)); \\ Antti Karttunen, Sep 21 2021

a(n) = A056239(n) - A346699(n).
a(n) = A346699(n) - A344616(n).
a(n even omega) = A346697(n).
a(n odd omega) = A346698(n).
A316524(n) = A346697(n) - A346698(n).
a(n) = A056239(A329888(n)). - Gus Wiseman and Antti Karttunen, Oct 13 2021

Data section extended up to 105 terms by Antti Karttunen, Sep 21 2021

A334108 a(n) = A331410(A122111(n)).

Original entry on oeis.org

0, 0, 0, 1, 0, 1, 0, 2, 2, 1, 0, 2, 0, 1, 2, 1, 0, 3, 0, 2, 2, 1, 0, 1, 3, 1, 4, 2, 0, 3, 0, 2, 2, 1, 3, 2, 0, 1, 2, 1, 0, 3, 0, 2, 4, 1, 0, 2, 4, 4, 2, 2, 0, 3, 3, 1, 2, 1, 0, 2, 0, 1, 4, 2, 3, 3, 0, 2, 2, 4, 0, 3, 0, 1, 5, 2, 4, 3, 0, 2, 2, 1, 0, 2, 3, 1, 2, 1, 0, 3, 4, 2, 2, 1, 3, 2, 0, 5, 4, 3, 0, 3, 0, 1, 5

Offset: 1

Antti Karttunen, Apr 29 2020

nonn

Antti Karttunen, Table of n, a(n) for n = 1..65537
Index entries for sequences computed from indices in prime factorization

Cf. A008578 (positions of zeros), A064989, A105560, A122111, A322865, A331410, A334107.

A064989(n) = {my(f); 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)};
A122111(n) = if(1==n,n,prime(bigomega(n))*A122111(A064989(n)));
A331410(n) = if(!bitand(n,n-1),0,1+A331410(n+(n/vecmax(factor(n)[, 1]))));
A334108(n) = A331410(A122111(n));

a(n) = A331410(A122111(n)) = A331410(A322865(n)).

a(n) = A331410(A105560(n)) + a(A064989(n)).

A334109 a(n) = A329697(A225546(n)).

Original entry on oeis.org

0, 0, 0, 1, 0, 0, 0, 1, 2, 0, 0, 1, 0, 0, 0, 1, 0, 2, 0, 1, 0, 0, 0, 1, 4, 0, 2, 1, 0, 0, 0, 1, 0, 0, 0, 3, 0, 0, 0, 1, 0, 0, 0, 1, 2, 0, 0, 1, 8, 4, 0, 1, 0, 2, 0, 1, 0, 0, 0, 1, 0, 0, 2, 2, 0, 0, 0, 1, 0, 0, 0, 3, 0, 0, 4, 1, 0, 0, 0, 1, 2, 0, 0, 1, 0, 0, 0, 1, 0, 2, 0, 1, 0, 0, 0, 1, 0, 8, 2, 5, 0, 0, 0, 1, 0

Offset: 1

Antti Karttunen, Apr 29 2020

nonn

Conjecture: Each k >= 0 occurs for the first time at A334110(k) = A019565(k)^2. Note that each k must occur first time on square n, because of the identity a(n) = a(A008833(n)). However, is there any reason to exclude squares with prime exponents > 2 from the candidates? See also comments in A334204.

Antti Karttunen, Table of n, a(n) for n = 1..10200
Antti Karttunen, Data supplement: n, a(n) computed for n = 1..65537

Cf. A001248, A005117 (positions of zeros), A334110.
Cf. A003961, A008833, A019565, A059895, A225546, A329697, A331590, A331736, A334204, A334860.
Cf. also A334107, A334108.

Map[-1 + Length@ NestWhileList[# - #/FactorInteger[#][[-1, 1]] &, #, # != 2^IntegerExponent[#, 2] &] &, Array[If[# == 1, 1, Times @@ Flatten@ Map[Function[{p, e}, Map[Prime[Log2@ # + 1]^(2^(PrimePi@ p - 1)) &, DeleteCases[NumberExpand[e, 2], 0]]] @@ # &, FactorInteger[#]]] &, 105] ] (* Michael De Vlieger, May 26 2020 *)

A019565(n) = factorback(vecextract(primes(logint(n+!n, 2)+1), n));
A329697(n) = if(!bitand(n,n-1),0,1+A329697(n-(n/vecmax(factor(n)[, 1]))));
A334109(n) = { my(f=factor(n),pis=apply(primepi,f[,1]),es=f[,2]); sum(k=1,#f~,(2^(pis[k]-1))*A329697(A019565(es[k]))); };

Additive with a(prime(i)^j) = A000079(i-1) * A329697(A019565(j)), a(m*n) = a(m)+a(n) if gcd(m,n) = 1.
Alternatively, additive with a(prime(i)^(2^k)) = 2^(i-1) * A329697(prime(k+1)), a(m*n) = a(m)+a(n) if A059895(m,n) = 1. - Peter Munn, May 04 2020
a(n) = A329697(A225546(n)) = A329697(A331736(n)).
a(n) = a(A008833(n)).
For all n >= 0, a(A334110(n)) = n, a(A334860(n)) = A334204(n).
a(A331590(m,k)) = a(m) + a(k); a(A003961(n)) = 2*a(n). - Peter Munn, Apr 30 2020

A339876 a(n) = A336466(A122111(n)).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 5, 1, 1, 1, 3, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 5, 1, 1, 1, 1, 1, 3, 1, 3, 1, 1, 1, 3, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 5, 1, 1, 1, 1, 1, 1, 1, 5, 9, 1, 1, 3, 1, 1, 1, 3, 1, 3, 1, 1, 1, 1, 1, 3, 1, 1, 1, 3, 1, 1, 1, 3, 1

Offset: 1

Antti Karttunen, Dec 25 2020

nonn

Antti Karttunen, Table of n, a(n) for n = 1..65537
Index entries for sequences computed from indices in prime factorization

Cf. A000265, A064989, A105560, A122111, A336466.

Cf. also A334107, A339877.

A000265(n) = (n>>valuation(n,2));
A122111(n) = if(1==n,n,my(f=factor(n), es=Vecrev(f[,2]),is=concat(apply(primepi,Vecrev(f[,1])),[0]),pri=0,m=1); for(i=1, #es, pri += es[i]; m *= prime(pri)^(is[i]-is[1+i])); (m));
A336466(n) = { my(f=factor(n)); prod(k=1,#f~,if(2==f[k,1],1,(A000265(f[k,1]-1))^f[k,2])); };
A339876(n) = A336466(A122111(n));

A064989(n) = {my(f); 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)};
A105560(n) = if(1==n,n,prime(bigomega(n)));
A339876(n) = if(1==n,n,A000265(A105560(n)-1) * A339876(A064989(n)));

a(1) = 1, for n > 1, a(n) = A000265(A105560(n)-1) * a(A064989(n)).

a(n) = A336466(A122111(n)).

A339874 Lexicographically earliest infinite sequence such that a(i) = a(j) => f(i) = f(j), where f(n) = A052126(n) for n > 1, and f(1) = 0.

Original entry on oeis.org

1, 2, 2, 3, 2, 3, 2, 4, 5, 3, 2, 4, 2, 3, 5, 6, 2, 7, 2, 4, 5, 3, 2, 6, 8, 3, 9, 4, 2, 7, 2, 10, 5, 3, 8, 11, 2, 3, 5, 6, 2, 7, 2, 4, 9, 3, 2, 10, 12, 13, 5, 4, 2, 14, 8, 6, 5, 3, 2, 11, 2, 3, 9, 15, 8, 7, 2, 4, 5, 13, 2, 16, 2, 3, 17, 4, 12, 7, 2, 10, 18, 3, 2, 11, 8, 3, 5, 6, 2, 14, 12, 4, 5, 3, 8, 15, 2, 19, 9, 20, 2, 7, 2, 6, 17

Offset: 1

Antti Karttunen, Dec 25 2020

nonn

For all i, j:
  A305800(i) = A305800(j) => a(i) = a(j),
  a(i) = a(j) => A001222(i) = A001222(j),
  a(i) = a(j) => A322826(i) = A322826(j).

Antti Karttunen, Table of n, a(n) for n = 1..65537

Cf. A052126, A322826.

Cf. also A305800, A300226, A334107, A334108.

up_to = 65537;
rgs_transform(invec) = { my(om = Map(), outvec = vector(length(invec)), u=1); for(i=1, length(invec), if(mapisdefined(om,invec[i]), my(pp = mapget(om, invec[i])); outvec[i] = outvec[pp] , mapput(om,invec[i],i); outvec[i] = u; u++ )); outvec; };
A052126(n) = if(1==n,n,(n/vecmax(factor(n)[, 1])));
Aux339874(n) = if(1==n,0,A052126(n));
v339874 = rgs_transform(vector(up_to, n, Aux339874(n)));
A339874(n) = v339874[n];

a(1) = 1; for n > 1, a(n) = 1 + A322826(n).

cp's OEIS Frontend

A329697 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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

PARI

Formula

A334201 a(n) = A056239(n) - A061395(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A346700 Sum of the even bisection (even-indexed parts) of the integer partition with Heinz number n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A334108 a(n) = A331410(A122111(n)).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A334109 a(n) = A329697(A225546(n)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A339876 a(n) = A336466(A122111(n)).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

PARI

Formula

A339874 Lexicographically earliest infinite sequence such that a(i) = a(j) => f(i) = f(j), where f(n) = A052126(n) for n > 1, and f(1) = 0.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula