A335912 -id:A335912 - cp's OEIS frontend

A335885 The length of a shortest path from n to a power of 2, when applying the nondeterministic maps k -> k - k/p and k -> k + k/p, where p can be any of the odd prime factors of k, and the maps can be applied in any order.

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

Offset: 1

Antti Karttunen, Jun 29 2020

nonn

The length of a shortest path from n to a power of 2, when using the transitions x -> A171462(x) and x -> A335876(x) in any order.

a((2^e)-1) is equal to A046051(e) = A001222((2^e)-1) when e is either a Mersenne exponent (in A000043), or some other number: 1, 4, 6, 8, 16, 32. For example, 32 is present because 2^32 - 1 = 4294967295 = 3*5*17*257*65537, a squarefree product of five known Fermat primes. - Antti Karttunen, Aug 11 2020

			A335876(67) = 68, and A171462(68) = 64 = 2^6, and this is the shortest path from 67 to a power of 2, thus a(67) = 2.
A171462(15749) = 15748, A335876(15748) = 15872, A335876(15872) = 16384 = 2^14, and this is the shortest path from 15749 to a power of 2, thus a(15749) = 3.

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

Cf. A000043, A046051, A052126, A171462, A335876, A335875, A335881, A335884, A335904, A335907.

Cf. A000079, A335911, A335912 (positions of 0's, 1's and 2's in this sequence) and array A335910.

A335885(n) = { my(f=factor(n)); sum(k=1,#f~,if(2==f[k,1],0,f[k,2]*(1+min(A335885(f[k,1]-1),A335885(f[k,1]+1))))); };

\\ Or empirically as:
A171462(n) = if(1==n,0,(n-(n/vecmax(factor(n)[, 1]))));
A335876(n) = if(1==n,2,(n+(n/vecmax(factor(n)[, 1]))));
A209229(n) = (n && !bitand(n,n-1));
A335885(n) = if(A209229(n),0,my(xs=Set([n]),newxs,a,b,u); for(k=1,oo, newxs=Set([]); for(i=1,#xs,u = xs[i]; a = A171462(u); if(A209229(a), return(k)); b = A335876(u); if(A209229(b), return(k)); newxs = setunion([a],newxs); newxs = setunion([b],newxs)); xs = newxs));

Fully additive with a(2) = 0, and a(p) = 1+min(a(p-1), a(p+1)), for odd primes p.
For all n >= 1, a(n) <= A335875(n) <= A335881(n) <= A335884(n) <= A335904(n).
For all n >= 0, a(A000244(n)) = n, and these also seem to give records.

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

Original entry on oeis.org

1, 2, 3, 4, 5, 9, 8, 6, 11, 27, 16, 7, 13, 33, 81, 32, 10, 15, 37, 99, 243, 64, 12, 18, 39, 107, 297, 729, 128, 14, 19, 43, 109, 321, 891, 2187, 256, 17, 21, 45, 111, 327, 963, 2673, 6561, 512, 20, 22, 53, 117, 333, 981, 2889, 8019, 19683, 1024, 24, 23, 54, 121, 351, 999, 2943, 8667, 24057, 59049, 2048, 28, 25, 55, 129, 363, 1053, 2997, 8829, 26001, 72171, 177147

Offset: 0

Antti Karttunen, Jul 01 2020

Array is read by descending antidiagonals with (n,k) = (0,0), (0,1), (1,0), (0,2), (1,1), (2,0), ... where A(n,k) is the (k+1)-th solution x to A335885(x) = n. The row indexing (n) starts from 0, and column indexing (k) also from 0.
For any odd prime p that appears on row n, either p-1 or p+1 appears 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 A335885 is completely additive.

			The top left corner of the array:
n\k |     0      1      2      3      4      5      6      7      8      9
----+--------------------------------------------------------------------------
  0 |     1,     2,     4,     8,    16,    32,    64,   128,   256,   512, ...
  1 |     3,     5,     6,     7,    10,    12,    14,    17,    20,    24, ...
  2 |     9,    11,    13,    15,    18,    19,    21,    22,    23,    25, ...
  3 |    27,    33,    37,    39,    43,    45,    53,    54,    55,    57, ...
  4 |    81,    99,   107,   109,   111,   117,   121,   129,   131,   135, ...
  5 |   243,   297,   321,   327,   333,   351,   363,   387,   393,   405, ...
  6 |   729,   891,   963,   981,   999,  1053,  1089,  1161,  1177,  1179, ...
  7 |  2187,  2673,  2889,  2943,  2997,  3159,  3267,  3483,  3531,  3537, ...
  8 |  6561,  8019,  8667,  8829,  8991,  9477,  9801, 10449, 10593, 10611, ...
  9 | 19683, 24057, 26001, 26487, 26973, 28431, 29403, 31347, 31779, 31833, ...

Index entries for sequences that are permutations of the natural numbers

Cf. A335885.
Cf. A000079, A335911, A335912 (rows 0-2), A000244 (is very like the leftmost column).
Cf. also arrays A334100, A335430.

up_to = 78-1; \\ = binomial(12+1,2)-1.
memoA335885 = Map();
A335885(n) = if(1==n,0,my(v=0); if(mapisdefined(memoA335885,n,&v), v, my(f=factor(n)); v = sum(k=1,#f~,if(2==f[k,1],0,f[k,2]*(1+min(A335885(f[k,1]-1),A335885(f[k,1]+1))))); mapput(memoA335885,n,v); (v)));
memoA335910sq = Map();
A335910sq(n, k) = { my(v=0); if((0==k), v = -1, if(!mapisdefined(memoA335910sq,[n,k-1],&v), v = A335910sq(n, k-1))); for(i=1+v,oo,if(A335885(1+i)==n,mapput(memoA335910sq,[n,k],i); return(1+i))); };
A335910list(up_to) = { my(v = vector(1+up_to), i=0); for(a=0,oo, for(col=0,a, i++; if(i > #v, return(v)); v[i] = A335910sq(col,(a-(col))))); (v); };
v335910 = A335910list(up_to);
A335910(n) = v335910[1+n];
for(n=0,up_to,print1(A335910(n),", "));

A335911 Numbers of the form q*(2^k), where k >= 0 and q is either a Fermat prime or a Mersenne prime; Numbers k for which A335885(k) = 1.

Original entry on oeis.org

3, 5, 6, 7, 10, 12, 14, 17, 20, 24, 28, 31, 34, 40, 48, 56, 62, 68, 80, 96, 112, 124, 127, 136, 160, 192, 224, 248, 254, 257, 272, 320, 384, 448, 496, 508, 514, 544, 640, 768, 896, 992, 1016, 1028, 1088, 1280, 1536, 1792, 1984, 2032, 2056, 2176, 2560, 3072, 3584, 3968, 4064, 4112, 4352, 5120, 6144, 7168, 7936, 8128, 8191

Offset: 1

Antti Karttunen, Jun 30 2020

nonn

Numbers k such that A000265(k) is either in A000668 or in A019434.

Product of any two terms (whether distinct or not) can be found in A335912.

Row 1 of A335910.
Union of A334101 and A335431. Subsequence of A038550.
Cf. A000668, A000668, A335885, A335912.
Cf. A141453 (after its initial 2, gives the primes present in this sequence).

A335885(n) = { my(f=factor(n)); sum(k=1,#f~,if(2==f[k,1],0,f[k,2]*(1+min(A335885(f[k,1]-1),A335885(f[k,1]+1))))); };
isA335911(n) = (1==A335885(n));

A000265(n) = (n>>valuation(n,2));
isA000668(n) = (isprime(n)&&!bitand(n,1+n));
isA019434(n) = ((n>2)&&isprime(n)&&!bitand(n-2, n-1));
isA335911(n) = (isA000668(A000265(n))||isA019434(A000265(n)));

A336115 Semiprimes that are product of a Fermat prime and a Mersenne prime.

Original entry on oeis.org

9, 15, 21, 35, 51, 93, 119, 155, 381, 527, 635, 771, 1799, 2159, 7967, 24573, 32639, 40955, 139247, 196611, 393213, 458759, 655355, 1572861, 2031647, 2105087, 2228207, 2621435, 8323199, 8912879, 33685247, 134741759, 536813567, 6442450941, 8590000127, 10737418235

Offset: 1

Antti Karttunen, Jul 09 2020

nonn

As 3 is both a Fermat prime and a Mersenne prime, A019434(1) * A000668(1) = 9 is also a term. It is the only square in this sequence.

Cf. A000265, A000668, A019434, A144482, A333788, A335885.

Subsequence of A335912.

isA000668(n) = (isprime(n)&&!bitand(n,1+n));
isA019434(n) = ((n>2)&&isprime(n)&&!bitand(n-2,n-1));
isA336115(n) = if(9==n,1, if((2!=omega(n))||(2!=bigomega(n)),0,my(ps=factor(n)[,1]); (isA019434(ps[1])&&isA000668(ps[2]))||(isA019434(ps[2])&&isA000668(ps[1])))); \\ Antti Karttunen, Jul 11 2020

A335885(a(n)) = 2.

Missing terms and more terms added by Jinyuan Wang, Jul 11 2020

A336122 Numbers k for which A335884(k) = 2.

Original entry on oeis.org

5, 7, 9, 10, 14, 18, 20, 28, 36, 40, 56, 72, 80, 112, 144, 160, 224, 288, 320, 448, 576, 640, 896, 1152, 1280, 1792, 2304, 2560, 3584, 4608, 5120, 7168, 9216, 10240, 14336, 18432, 20480, 28672, 36864, 40960, 57344, 73728, 81920, 114688, 147456, 163840, 229376, 294912, 327680, 458752, 589824, 655360, 917504, 1179648, 1310720

Offset: 1

Antti Karttunen, Jul 09 2020

nonn

Numbers n such that when we start from k = n, and apply in any combination the nondeterministic maps k -> k - k/p and k -> k + k/p, (where p can be any of the odd prime factors of k), a power of 2 will appear no later than after two such steps, and on some of the combinations a power of 2 will appear after exactly two steps.

Cf. A335884.

Cf. also A334102, A335882, A335912.

A335884(n) = { my(f=factor(n)); sum(k=1,#f~,if(2==f[k,1],0,f[k,2]*(1+max(A335884(f[k,1]-1),A335884(f[k,1]+1))))); };
isA336122(n) = (2==A335884(n));

cp's OEIS Frontend

A335885 The length of a shortest path from n to a power of 2, when applying the nondeterministic maps k -> k - k/p and k -> k + k/p, where p can be any of the odd prime factors of k, and the maps can be applied in any order.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

PARI

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A335911 Numbers of the form q*(2^k), where k >= 0 and q is either a Fermat prime or a Mersenne prime; Numbers k for which A335885(k) = 1.

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI

PARI

A336115 Semiprimes that are product of a Fermat prime and a Mersenne prime.

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI

Formula

Extensions

A336122 Numbers k for which A335884(k) = 2.

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI