A329697 -id:A329697

A334100

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

+20
17

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

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

1,2

COMMENTS

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.

LINKS

Table of n, a(n) for n=1..78.

Index entries for sequences that are permutations of the natural numbers

EXAMPLE

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.

MATHEMATICA

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 *)

PROG

(PARI)

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];

CROSSREFS

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.

KEYWORD

nonn,tabl

AUTHOR

Antti Karttunen, Apr 14 2020

STATUS

approved

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.

+20
14

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,1

COMMENTS

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

LINKS

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

PROG

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

(PARI)

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)));

(PARI) 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)<lim, if(isprime(t+1), listput(v, t+1)))); Set(v) \\ Charles R Greathouse IV, Apr 14 2020

CROSSREFS

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.

KEYWORD

nonn

AUTHOR

Antti Karttunen, Apr 14 2020

EXTENSIONS

More terms from Giovanni Resta, Apr 14 2020

STATUS

approved

A334102

Numbers n for which A329697(n) == 2.

+20
14

7, 9, 11, 13, 14, 15, 18, 22, 25, 26, 28, 30, 36, 41, 44, 50, 51, 52, 56, 60, 72, 82, 85, 88, 97, 100, 102, 104, 112, 120, 137, 144, 164, 170, 176, 193, 194, 200, 204, 208, 224, 240, 274, 288, 289, 328, 340, 352, 386, 388, 400, 408, 416, 448, 480, 548, 576, 578, 641, 656, 680, 704, 769, 771, 772, 776, 800, 816, 832, 896, 960, 1096

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,1

COMMENTS

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

Numbers k such that A000265(k) is either in A333788 or in A334092.

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

Binary weight (A000120) of these terms is always either 2, 3 or 4. It is 2 for those terms that are of the form 9*2^k, 4 for the terms of the form p*q*2^k, where p and q are two distinct Fermat primes (A019434), and 3 for the both terms of the form A334092(n)*2^k, and for the terms of the form (p^2)*(2^k), where p is a Fermat prime > 3.

LINKS

Table of n, a(n) for n=1..72.

PROG

(PARI)

A000265(n) = (n>>valuation(n, 2));

isA019434(n) = ((n>2)&&isprime(n)&&!bitand(n-2, n-1)); \\ Charfun for A019434, Fermat primes.

isA334102(n) = { n = A000265(n); if(isprime(n), isA019434(A000265(n-1)), if(bigomega(n)!=2, 0, factorback(apply(isA019434, factor(n)[, 1])))); };

(PARI)

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

isA334102(n) = (2==A329697(n));

CROSSREFS

Row 2 of A334100.

Cf. A000120, A000265, A019434, A052126, A171462, A209229, A329697.

Cf. A333788 (a subsequence), A334092 (primes present), A334093 (primes that are 1 + some term in this sequence).

Squares of A334101 form a subsequence of this sequence. Squares of these numbers can be found (as a subset) in A334104, and the cubes in A334106.

KEYWORD

nonn

AUTHOR

Antti Karttunen, Apr 14 2020

STATUS

approved

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.

+20
13

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,1

COMMENTS

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.

LINKS

Table of n, a(n) for n=1..57.

FORMULA

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

PROG

(PARI)

A000265(n) = (n>>valuation(n, 2));

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

isA334101(n) = isA019434(A000265(n));

(PARI)

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)));

CROSSREFS

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.

KEYWORD

nonn

AUTHOR

Antti Karttunen, Apr 14 2020

STATUS

approved

A334204

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

+20
12

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,6

COMMENTS

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.

LINKS

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

Index entries for sequences related to binary expansion of n

FORMULA

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.

PROG

(PARI)

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));

CROSSREFS

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

KEYWORD

nonn

AUTHOR

Antti Karttunen, Jun 09 2020

STATUS

approved

A335880

Lexicographically earliest infinite sequence such that a(i) = a(j) => A329697(i) = A329697(j) and A331410(i) = A331410(j) for all i, j >= 1.

+20
11

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,3

COMMENTS

Restricted growth sequence transform of the ordered pair [A329697(n), A331410(n)].

For all i, j:

A324400(i) = A324400(j) => a(i) = a(j),

a(i) = a(j) => A334861(i) = A334861(j),

a(i) = a(j) => A335875(i) = A335875(j),

a(i) = a(j) => A335877(i) = A335877(j),

a(i) = a(j) => A335881(i) = A335881(j).

LINKS

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

PROG

(PARI)

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; };

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

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

Aux335880(n) = [A329697(n), A331410(n)];

v335880 = rgs_transform(vector(up_to, n, Aux335880(n)));

A335880(n) = v335880[n];

CROSSREFS

Cf. A329697, A331410, A334861, A335875, A335877, A335881.

Cf. also A324400, A334867.

KEYWORD

nonn

AUTHOR

Antti Karttunen, Jun 29 2020

STATUS

approved

A336694

a(n) = A329697(1+sigma(n)), where A329697 is totally additive with a(2) = 0 and a(p) = 1 + a(p-1) for odd primes.

+20
11

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,5

LINKS

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

Index entries for sequences related to sigma(n)

FORMULA

a(n) = A329697(1+A000203(n)) = A329697(A088580(n)) = A329697(A332459(n)).

PROG

(PARI)

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

A336694(n) = A329697(1+sigma(n));

CROSSREFS

Cf. A000203, A088580, A324294, A329697, A332459, A336691, A336692, A336693, A336695, A336696.

KEYWORD

nonn

AUTHOR

Antti Karttunen, Jul 31 2020

STATUS

approved

A334103

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

+20
10

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,1

COMMENTS

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.

LINKS

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

PROG

(PARI)

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

isA334103(n) = (3==A329697(n));

CROSSREFS

Row 3 of A334100.

Cf. A052126, A171462, A209229, A329697, A334101, A334102, A334104, A334106.

Cf. A334093 (primes present), A334094.

KEYWORD

nonn

AUTHOR

Antti Karttunen, Apr 14 2020

STATUS

approved

A334104

Numbers m for which A329697(m) = 4.

+20
10

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,1

COMMENTS

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.

LINKS

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

EXAMPLE

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.

MATHEMATICA

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

PROG

(PARI)

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

isA334104(n) = (4==A329697(n));

CROSSREFS

Row 4 of A334100.

Cf. A052126, A171462, A209229, A329697, A334101, A334102, A334103, A334105, A334106.

Cf. A334094 (primes present).

KEYWORD

nonn

AUTHOR

Antti Karttunen, Apr 14 2020

STATUS

approved

A336469

a(n) = A329697(phi(n)), where A329697 is totally additive with a(2) = 0 and a(p) = 1 + a(p-1) for odd primes.

+20
10

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,19

LINKS

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

FORMULA

Additive with a(2^e) = 0, and for odd primes p, a(p^e) = A329697((p - 1)*p^(e-1)) = e*A329697(p) - 1.

a(n) = A329697(n) - A005087(n) = A336396(n) + A046660(A000265(n)).

MATHEMATICA

Array[Length@ NestWhileList[# - #/FactorInteger[#][[-1, 1]] &, EulerPhi[#], # != 2^IntegerExponent[#, 2] &] - 1 &, 105] (* Michael De Vlieger, Jul 24 2020 *)

PROG

(PARI)

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

A336469(n) = A329697(eulerphi(n));

\\ Or alternatively as:

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

CROSSREFS

Cf. A000010, A000265, A003434, A005087, A046660, A064097, A064415, A329697, A336396, A336477.

Cf. A003401 (positions of zeros).

KEYWORD

nonn

AUTHOR

Antti Karttunen, Jul 22 2020

STATUS

approved