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

A334100 Square array where the row n lists all numbers k for which A329697(k) = n, read by falling antidiagonals.

Original entry on oeis.org

1, 2, 3, 4, 5, 7, 8, 6, 9, 19, 16, 10, 11, 21, 43, 32, 12, 13, 23, 47, 127, 64, 17, 14, 27, 49, 129, 283, 128, 20, 15, 29, 57, 133, 301, 659, 256, 24, 18, 31, 59, 139, 329, 817, 1319, 512, 34, 22, 33, 63, 141, 343, 827, 1699, 3957, 1024, 40, 25, 35, 67, 147, 347, 839, 1787, 4079, 9227, 2048, 48, 26, 37, 69, 161, 361, 849, 1849, 4613, 9233, 21599

Offset: 1

Antti Karttunen, Apr 14 2020

Array is read by descending antidiagonals with (n,k) = (0,1), (0,2), (1,1), (0,3), (1,2), (2,1), ... where A(n,k) is the k-th solution x to A329697(x) = n. The row indexing (n) starts from 0, and column indexing (k) from 1.
Any odd prime that appears on row n is 1+{some term on row n-1}.
The e-th powers of the terms on row n form a subset of terms on row (e*n). More generally, a product of terms that occur on rows i_1, i_2, ..., i_k can be found at row (i_1 + i_2 + ... + i_k), because A329697 is completely additive.
The binary weight (A000120) of any term on row n is at most 2^n.

			The top left corner of the array:
  n\k |    1     2     3     4     5     6     7     8     9    10
------+----------------------------------------------------------------
   0  |    1,    2,    4,    8,   16,   32,   64,  128,  256,  512, ...
   1  |    3,    5,    6,   10,   12,   17,   20,   24,   34,   40, ...
   2  |    7,    9,   11,   13,   14,   15,   18,   22,   25,   26, ...
   3  |   19,   21,   23,   27,   29,   31,   33,   35,   37,   38, ...
   4  |   43,   47,   49,   57,   59,   63,   67,   69,   71,   77, ...
   5  |  127,  129,  133,  139,  141,  147,  161,  163,  171,  173, ...
   6  |  283,  301,  329,  343,  347,  361,  379,  381,  383,  387, ...
   7  |  659,  817,  827,  839,  849,  863,  883,  889,  893,  903, ...
   8  | 1319, 1699, 1787, 1849, 1977, 1979, 1981, 2021, 2039, 2083, ...
   9  | 3957, 4079, 4613, 4903, 5097, 5179, 5361, 5377, 5399, 5419, ...
etc.
Note that the row 9 is the first one which begins with composite, as 3957 = 3*1319. The next such rows are row 15 and row 22. See A334099.

Index entries for sequences that are permutations of the natural numbers

Cf. A329697.
Cf. A334099 (the leftmost column).
Cf. A000079, A334101, A334102, A334103, A334104, A334105, A334106 for the rows 0-6.
Cf. A019434, A334092, A334093, A334094, A334095, A334096 for the primes on the rows 1-6.
Cf. also irregular triangle A334111.

Block[{nn = 16, s}, s = Values@ PositionIndex@ Array[-1 + Length@ NestWhileList[# - #/FactorInteger[#][[-1, 1]] &, #, # != 2^IntegerExponent[#, 2] &] &, 2^nn]; Table[s[[#, k]] &[m - k + 1], {m, nn - Ceiling[nn/4]}, {k, m, 1, -1}]] // Flatten (* Michael De Vlieger, Apr 30 2020 *)

up_to = 105; \\ up_to = 1081; \\ = binomial(46+1,2)
A329697(n) = if(!bitand(n,n-1),0,1+A329697(n-(n/vecmax(factor(n)[, 1]))));
memoA334100sq = Map();
A334100sq(n, k) = { my(v=0); if(!mapisdefined(memoA334100sq,[n,k-1],&v),if(1==k, v=0, v = A334100sq(n, k-1))); for(i=1+v,oo,if(A329697(i)==(n-1),mapput(memoA334100sq,[n,k],i); return(i))); };
A334100list(up_to) = { my(v = vector(up_to), i=0); for(a=1,oo, for(col=1,a, i++; if(i > up_to, return(v)); v[i] = A334100sq(col,(a-(col-1))))); (v); };
v334100 = A334100list(up_to);
A334100(n) = v334100[n];

A334092 Primes p of the form of the form q*2^h + 1, where q is one of the Fermat primes; Primes p for which A329697(p) == 2.

Original entry on oeis.org

7, 11, 13, 41, 97, 137, 193, 641, 769, 12289, 40961, 163841, 557057, 786433, 167772161, 2281701377, 3221225473, 206158430209, 2748779069441, 6597069766657, 38280596832649217, 180143985094819841, 221360928884514619393, 188894659314785808547841, 193428131138340667952988161

Offset: 1

Antti Karttunen, Apr 14 2020

nonn

Primes p such that p-1 is not a power of two, but for which A171462(p-1) = (p-1-A052126(p-1)) is [a power of 2].

Primes of the form ((2^(2^k))+1)*2^h + 1, where ((2^(2^k))+1) is one of the Fermat primes, A019434, 3, 5, 17, 257, ..., .

Charles R Greathouse IV, Table of n, a(n) for n = 1..53

Primes in A334102.
Intersection of A081091 and A147545.
Subsequences: A039687, A050526, A300407.
Cf. A000040, A010051, A019434, A052126, A171462, A329697. Cf. also A334093, A334094, A334095, A334096.

isA334092(n) = (isprime(n)&&2==A329697(n));

A052126(n) = if(1==n,n,n/vecmax(factor(n)[, 1]));
A209229(n) = (n && !bitand(n,n-1));
isA334092(n) = (isprime(n)&&(!A209229(n-1))&&A209229(n-1-A052126(n-1)));

list(lim)=if(exponent(lim\=1)>=2^33, error("Verify composite character of more Fermat primes before checking this high")); my(v=List(),t); for(e=0,4, t=2^2^e+1; while((t<<=1)Charles R Greathouse IV, Apr 14 2020

More terms from Giovanni Resta, Apr 14 2020

A334101 Numbers of the form q*(2^k), where q is one of the Fermat primes and k >= 0; Numbers n for which A329697(n) == 1.

Original entry on oeis.org

3, 5, 6, 10, 12, 17, 20, 24, 34, 40, 48, 68, 80, 96, 136, 160, 192, 257, 272, 320, 384, 514, 544, 640, 768, 1028, 1088, 1280, 1536, 2056, 2176, 2560, 3072, 4112, 4352, 5120, 6144, 8224, 8704, 10240, 12288, 16448, 17408, 20480, 24576, 32896, 34816, 40960, 49152, 65537, 65792, 69632, 81920, 98304, 131074, 131584, 139264

Offset: 1

Antti Karttunen, Apr 14 2020

nonn

Numbers k that themselves are not powers of two, but for which A171462(k) = k-A052126(k) is [a power of 2].
Numbers k such that A000265(k) is in A019434.
Squares of these numbers can be found (as a subset) in A334102, and the cubes (as a subset) in A334103.

Row 1 of A334100.
Cf. A000120, A000265, A052126, A171462, A209229, A329697, A334102, A334103.
Cf. A019434 (primes present), A007283, A020714, A110287 (other subsequences).
Subsequence of A018900.

A000265(n) = (n>>valuation(n,2));
isA019434(n) = ((n>2)&&isprime(n)&&!bitand(n-2,n-1));
isA334101(n) = isA019434(A000265(n));

A052126(n) = if(1==n,n,n/vecmax(factor(n)[, 1]));
A209229(n) = (n && !bitand(n,n-1));
isA334101(n) = ((!A209229(n))&&A209229(n-A052126(n)));

For all n, A000120(a(n)) = 2.

A334103 Numbers n for which A329697(n) == 3.

Original entry on oeis.org

19, 21, 23, 27, 29, 31, 33, 35, 37, 38, 39, 42, 45, 46, 53, 54, 55, 58, 61, 62, 65, 66, 70, 73, 74, 75, 76, 78, 83, 84, 89, 90, 92, 101, 103, 106, 108, 110, 113, 116, 119, 122, 123, 124, 125, 130, 132, 140, 146, 148, 150, 152, 153, 156, 166, 168, 178, 180, 184, 187, 202, 205, 206, 212, 216, 220, 221, 226, 232, 238, 241, 244

Offset: 1

Antti Karttunen, Apr 14 2020

nonn

Numbers n for which A171462(n) = n-A052126(n) is in A334102.

Among the first 2821 terms (terms < 2^31), there are terms with binary weights 2, 3, 4, 5, 6 and 8. For example, 33 is the first term with binary weight 2, and 255 is the first term with binary weight 8.

Antti Karttunen, Table of n, a(n) for n = 1..2821; all terms <= 2^31

Row 3 of A334100.
Cf. A052126, A171462, A209229, A329697, A334101, A334102, A334104, A334106.
Cf. A334093 (primes present), A334094.

A329697(n) = if(!bitand(n,n-1),0,1+A329697(n-(n/vecmax(factor(n)[, 1]))));
isA334103(n) = (3==A329697(n));

A334104 Numbers m for which A329697(m) = 4.

Original entry on oeis.org

43, 47, 49, 57, 59, 63, 67, 69, 71, 77, 79, 81, 86, 87, 91, 93, 94, 95, 98, 99, 105, 107, 109, 111, 114, 115, 117, 118, 121, 126, 131, 134, 135, 138, 142, 143, 145, 149, 151, 154, 155, 157, 158, 159, 162, 165, 167, 169, 172, 174, 175, 179, 181, 182, 183, 185, 186, 188, 190, 195, 196, 198, 210, 214, 218, 219, 222, 225

Offset: 1

Antti Karttunen, Apr 14 2020

nonn

Squares of A334102 form a subsequence.

Among the first 12193 terms (terms < 2^31), there are terms with binary weights 2 - 16, except no terms with weight 13, 14 or 15. For example, 1025 is the first term with binary weight 2, and 65535 is the first term with binary weight 16.

			63 = 7*9 is a term as both 7 and 9 are terms of A334102.
65535 = 3*5*17*257 is a term as it is a product of four Fermat primes, thus in four steps all odd primes can be eliminated with p -> (p-1) map.

Antti Karttunen, Table of n, a(n) for n = 1..12193; all terms <= 2^31

Row 4 of A334100.
Cf. A052126, A171462, A209229, A329697, A334101, A334102, A334103, A334105, A334106.
Cf. A334094 (primes present).

Position[Array[Length@NestWhileList[# - #/FactorInteger[#][[-1, 1]] &, #, # != 2^IntegerExponent[#, 2] &] - 1 &, 225], 4][[All, 1]] (* Michael De Vlieger, Apr 30 2020 *)

A329697(n) = if(!bitand(n,n-1),0,1+A329697(n-(n/vecmax(factor(n)[, 1]))));
isA334104(n) = (4==A329697(n));

A335882 Numbers k for which A331410(k) = 2.

Original entry on oeis.org

5, 9, 10, 11, 13, 18, 20, 21, 22, 23, 26, 36, 40, 42, 44, 46, 47, 49, 52, 61, 72, 80, 84, 88, 92, 93, 94, 98, 104, 122, 144, 160, 168, 176, 184, 186, 188, 191, 196, 208, 217, 223, 244, 288, 320, 336, 352, 368, 372, 376, 381, 382, 383, 392, 416, 434, 446, 488, 576, 640, 672, 704, 736, 744, 752, 762, 764, 766, 784, 832, 868, 889, 892, 961

Offset: 1

Antti Karttunen, Jun 28 2020

nonn

Numbers k such that A000265(k) is either in A144482 or in A335874.

Each term is either of the form A335874(n)*2^k, for some n >= 2, and k >= 0, or a product of two terms of A335431, whether distinct or not.

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

Row 2 of A335430.
Cf. A331410, A335431, A335874 (after its initial 2, gives the primes in this sequence), A144482 (odd semiprimes in this sequence).
Cf. also A334102.

A000265(n) = (n>>valuation(n,2));
isA000668(n) = (isprime(n)&&!bitand(n,1+n));
isA144482(n) = ((2==bigomega(n))&&isA000668(vecmin(factor(n)[,1]))&&isA000668(vecmax(factor(n)[,1])));
isA335874(n) = ((n>2)&&isprime(n)&&isA000668(A000265(1+n)));
isA335882(n) = (isA335874(A000265(n))||isA144482(A000265(n)));

A334093 Primes p for which A329697(p) == 3.

Original entry on oeis.org

19, 23, 29, 31, 37, 53, 61, 73, 83, 89, 101, 103, 113, 241, 353, 389, 401, 409, 449, 577, 773, 1097, 1153, 1283, 1361, 1409, 1543, 1553, 1601, 3089, 3329, 5441, 6529, 7681, 13313, 15361, 17477, 18433, 25601, 26113, 49157, 49409, 61441, 82241, 83969, 87041, 98689, 114689, 147457, 295937, 327689, 328961, 417793

Offset: 1

Antti Karttunen, Apr 14 2020

nonn

Primes p of the form of the form A334102(n) + 1, for some n >= 1.

Cf. A329697, A334102, primes in A334103.

Cf. also A019434, A334092, A334094, A334095, A334096.

A329697(n) = if(!bitand(n,n-1),0,1+A329697(n-(n/vecmax(factor(n)[, 1]))));
isA334093(n) = (isprime(n)&&(3==A329697(n)));

A334106 Numbers n for which A329697(n) == 6.

Original entry on oeis.org

283, 301, 329, 343, 347, 361, 379, 381, 383, 387, 399, 413, 417, 419, 423, 431, 437, 441, 463, 469, 473, 483, 487, 489, 491, 497, 509, 513, 517, 519, 523, 529, 531, 539, 547, 551, 553, 557, 559, 566, 567, 571, 573, 589, 591, 597, 599, 602, 603, 609, 611, 621, 627, 631, 633, 635, 637, 639, 643, 645, 649, 651, 653, 658, 665

Offset: 1

Antti Karttunen, Apr 14 2020

nonn

Antti Karttunen, Table of n, a(n) for n = 1..12096; all terms < 2^17

Row 6 of A334100.
Cf. A052126, A171462, A209229, A329697, A334101, A334102, A334103, A334104, A334105.
Cf. A334096 (primes present).

A329697(n) = if(!bitand(n,n-1),0,1+A329697(n-(n/vecmax(factor(n)[, 1]))));
isA334106(n) = (6==A329697(n));

A334105 Numbers m for which A329697(m) = 5.

Original entry on oeis.org

127, 129, 133, 139, 141, 147, 161, 163, 171, 173, 177, 189, 191, 197, 199, 201, 203, 207, 209, 211, 213, 215, 217, 223, 229, 231, 235, 237, 243, 245, 247, 253, 254, 258, 259, 261, 263, 266, 269, 271, 273, 277, 278, 279, 282, 285, 294, 295, 297, 299, 311, 315, 317, 319, 321, 322, 326, 327, 331, 333, 335, 341, 342, 345, 346, 349, 351

Offset: 1

Antti Karttunen, Apr 14 2020

nonn

			127 = 63*2 + 1 is a term, as 127 is a prime and 63 is in A334104 as A329697(63) = 4.
2^32 -1 = 4294967295 = 3*5*17*257*65537 is a term as it is a product of five Fermat primes, thus in five steps all odd primes can be eliminated with p -> (p-1) map.
Likewise for 1442840405 = 5 * 17 * 257^3. (The first term with binary weight = 24).

Antti Karttunen, Table of n, a(n) for n = 1..50071; all terms < 2^31

Row 5 of A334100.
Cf. A052126, A171462, A209229, A329697, A334101, A334102, A334103, A334104, A334106.
Cf. A334095 (primes present).

Position[Array[Length@ NestWhileList[# - #/FactorInteger[#][[-1, 1]] &, #, # != 2^IntegerExponent[#, 2] &] - 1 &, 360], 5][[All, 1]] (* Michael De Vlieger, Apr 30 2020 *)

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

A334100 Square array where the row n lists all numbers k for which A329697(k) = n, read by falling antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A334092 Primes p of the form of the form q*2^h + 1, where q is one of the Fermat primes; Primes p for which A329697(p) == 2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

PARI

PARI

Extensions

A334101 Numbers of the form q*(2^k), where q is one of the Fermat primes and k >= 0; Numbers n for which A329697(n) == 1.

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI

PARI

Formula

A334103 Numbers n for which A329697(n) == 3.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

A334104 Numbers m for which A329697(m) = 4.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A335882 Numbers k for which A331410(k) = 2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

A334093 Primes p for which A329697(p) == 3.

Views

Author