A334109 -id:A334109 - 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)

A334204 a(n) = A329697(A163511(n)).

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Jun 09 2020

nonn

As the underlying sequence A163511 can be represented as a binary tree, so can be this:
                                     0
                                     |
                  ...................0...................
                 0                                       1
       0......../ \........2                   1......../ \........1
      / \                 / \                 / \                 / \
     /   \               /   \               /   \               /   \
    /     \             /     \             /     \             /     \
   0       3           2       2           1       2           1       2
  0 4     3 3         2 3     2 4         1 3     2 3         1 3     2 2
etc.
The nodes at the left edge are all zeros, and their right-hand children give positive integers, A000027.
Each left-hand leaning branch stays constant, because A329697(2n) = A329697(n).
The right-hand leaning branches are not necessarily monotonic. For example, a((2^6)-1) = 2 > 1 = a((2^7)-1), because A000040(7) = 17 is a Fermat prime (but A000040(6) = 13 is not), and therefore the latter is only one step away from a power of 2.

Antti Karttunen, Table of n, a(n) for n = 0..65537
Index entries for sequences related to binary expansion of n

Cf. A000079, A163511, A329697, A334109, A334860, A334867, A334873.

A005940(n) = { my(p=2, t=1); n--; until(!n\=2, if((n%2), (t*=p), p=nextprime(p+1))); t }; \\ From A005940
A054429(n) = ((3<<#binary(n\2))-n-1); \\ From A054429
A163511(n) = if(!n,1,A005940(1+A054429(n)));
A329697(n) = if(!bitand(n,n-1),0,1+A329697(n-(n/vecmax(factor(n)[, 1]))));
A334204(n) = A329697(A163511(n));

a(n) = A329697(A163511(n)).
a(n) = A334109(A334860(n)).
a(n) = a(2n) = a(A000265(n)).
For all n >= 0, a(2^n) = 0, a(2^n + 1) = n.

A334860 a(0) = 1, a(1) = 2, after which, a(2n) = A334747(a(n)), a(2n+1) = a(n)^2.

Original entry on oeis.org

1, 2, 3, 4, 6, 9, 8, 16, 5, 36, 18, 81, 12, 64, 32, 256, 10, 25, 72, 1296, 27, 324, 162, 6561, 24, 144, 128, 4096, 48, 1024, 512, 65536, 15, 100, 50, 625, 108, 5184, 2592, 1679616, 54, 729, 648, 104976, 243, 26244, 13122, 43046721, 20, 576, 288, 20736, 192, 16384, 8192, 16777216, 96, 2304, 2048, 1048576, 768, 262144, 131072, 4294967296, 30

Offset: 0

Antti Karttunen, Jun 08 2020

This irregular table can be represented as a binary tree. Each child to the left is obtained by applying A334747 to the parent, and each child to the right is obtained by squaring the parent:
                                      1
                                      |
                   ...................2...................
                  3                                       4
        6......../ \........9                   8......../ \........16
       / \                 / \                 / \                 / \
      /   \               /   \               /   \               /   \
     /     \             /     \             /     \             /     \
    5       36         18       81         12       64         32      256
  10 25   72  1296   27  324 162  6561   24  144  128 4096   48 1024 512 65536
etc.
This is the mirror image of the tree in A334866.
Fermi-Dirac primes, A050376, occur at rightward growing branches that originate from primes situated at the left edge.
The tree illustrated in A163511 is expanded as x -> 2*x for the left child and x -> A003961(x) for the right child, while this tree is expanded as x -> A225546(2*A225546(x)) for the left child, and x -> A225546(A003961(A225546(x))) for the right child.

Index entries for sequences that are permutations of the natural numbers

Cf. A000290, A225546, A334204, A334747, A334859 (inverse), A334866 (mirror image).
Cf. A001146 (right edge of the tree), A019565 (left edge), A334110 (the right children of the left edge).
Composition of permutations A163511 and A225546.

A334747(n) = { my(c=core(n), m=n); forprime(p=2, , if(c % p, m*=p; break, m/=p)); m; }; \\ From A334747
A334860(n) = if(n<=1,1+n,if(!(n%2),A334747(A334860(n/2)),A334860((n-1)/2)^2));

a(0) = 1, a(1) = 2; and for n > 0, a(2n) = A334747(a(n)), a(2n+1) = a(n)^2.
a(n) = A225546(A163511(n)).
For n >= 0, a(2^n) = A019565(1+n), a(2^((2^n)-1)) = A000040(1+n).
A334109(a(n)) = A334204(n).
It seems that for n >= 1, A048675(a(n)) = A135529(n) = A048675(A163511(n)).

A334107 a(n) = A329697(A122111(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, 2, 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, 2, 0, 4, 2, 4, 0, 2, 0, 2, 3

Offset: 1

Antti Karttunen, Apr 29 2020

nonn

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

Cf. A001248, A008578 (positions of zeros), A064989, A105560, A122111, A322865, A329697, A334108, A334109, A334201.

Map[Length@ NestWhileList[# - #/FactorInteger[#][[-1, 1]] &, #, # != 2^IntegerExponent[#, 2] &] - 1 &, Array[Times @@ Table[Prime[LengthWhile[#1, # >= j &] /. 0 -> 1], {j, #2}] & @@ {#, Max[#]} &@ PrimePi@ Flatten[ConstantArray[#1, {#2}] & @@@ FactorInteger@ #] &, 105] ] (* Michael De Vlieger, May 14 2020, after Robert G. Wilson v at A329697 *)

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)));
A329697(n) = if(!bitand(n,n-1),0,1+A329697(n-(n/vecmax(factor(n)[, 1]))));
A334107(n) = A329697(A122111(n));

a(n) = A329697(A122111(n)) = A329697(A322865(n)).
a(n) = A329697(A105560(n)) + a(A064989(n)).
For n >= 1, a(A001248(n)) = n, and these seem to be also the first occurrences of each n.

A334110 The squares of squarefree numbers (A062503), ordered lexicographically according to their prime factors. a(n) = Product_{k in I} prime(k+1)^2, where I are the indices of nonzero binary digits in n = Sum_{k in I} 2^k.

Original entry on oeis.org

1, 4, 9, 36, 25, 100, 225, 900, 49, 196, 441, 1764, 1225, 4900, 11025, 44100, 121, 484, 1089, 4356, 3025, 12100, 27225, 108900, 5929, 23716, 53361, 213444, 148225, 592900, 1334025, 5336100, 169, 676, 1521, 6084, 4225, 16900, 38025, 152100, 8281, 33124, 74529, 298116, 207025, 828100, 1863225, 7452900, 20449, 81796, 184041

Offset: 0

Antti Karttunen and Peter Munn, May 01 2020

nonn

For the lexicographic ordering, the prime factors must be written in nonincreasing order. If we write the factors in nondecreasing order, we get a lexicographically ordered set with an order type that is greater than a natural number index - the resulting sequence does not include all qualifying numbers. (Note also that the symbols used for the lexicographic order are the prime numbers, not their digits.)
a(n) is the n-th power of 4 in the monoid defined in A331590.
Conjecture: a(n) is the position of the first occurrence of n in A334109.

			The initial terms are shown below, equated with the product of their prime factors to exhibit the lexicographic ordering. The list starts with 1, since 1 is factored as the empty product and the empty list is first in lexicographic order.
    1 = .
    4 = 2*2.
    9 = 3*3.
   36 = 3*3*2*2.
   25 = 5*5.
  100 = 5*5*2*2.
  225 = 5*5*3*3.
  900 = 5*5*3*3*2*2.
   49 = 7*7.
  196 = 7*7*2*2.
  441 = 7*7*3*3.

Cf. A000079, A019565 (square roots), A048675, A097248, A225546, A267116, A332382, A334109 (a left inverse).
Column 2 of A329332. Permutation of A062503.
After 1, the right children of the leftmost edge of A334860, or respectively, the left children of the rightmost edge of A334866.
Subsequences: A001248, A061742, A166329.
Subsequence of A052330.
A003961, A003987, A059897, A331590 are used to express relationship between terms of this sequence.

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

A334110(n) = { my(p=2,m=1); while(n, if(n%2, m *= p^2); n >>= 1; p = nextprime(1+p)); (m); };

a(n) = A019565(n)^2.
For n >= 1, a(A000079(n-1)) = A001248(n).
For all n >= 0, A334109(a(n)) = n.
a(n+k) = A331590(a(n), a(k)).
a(n XOR k) = A059897(a(n), a(k)), where XOR denotes bitwise exclusive-or, A003987.
a(n) = A225546(3^n).
a(2n) = A003961(a(n)).
a(2n+1) = 4 * a(2n).
a(2^k-1) = A061742(k).
A267116(a(n)) = 2.
A048675(a(n)) = 2n.
A097248(a(n)) = A332382(n) = A019565(2n).

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

A334204 a(n) = A329697(A163511(n)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A334860 a(0) = 1, a(1) = 2, after which, a(2n) = A334747(a(n)), a(2n+1) = a(n)^2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A334107 a(n) = A329697(A122111(n)).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A334110 The squares of squarefree numbers (A062503), ordered lexicographically according to their prime factors. a(n) = Product_{k in I} prime(k+1)^2, where I are the indices of nonzero binary digits in n = Sum_{k in I} 2^k.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

Formula