A054432 -id:A054432 - cp's OEIS frontend

A306388 a(n) is a decimal number k having a length n binary expansion which encodes, from left to right at digit j, the coprimality (0) or non-coprimality (1) of j to n, for 1 < j <= n, except for the first digit, which is always 1.

1, 3, 5, 13, 17, 61, 65, 213, 329, 885, 1025, 3933, 4097, 13781, 22121, 54613, 65537, 251741, 262145, 906613, 1364681, 3497301, 4194305, 16111453, 17859617, 55932245, 86282825, 225793493, 268435457, 1064687485, 1073741825, 3579139413, 5526297161, 14316688725

Offset: 1

Christopher Hohl, Mar 01 2019

Let Sum* be a special summation procedure carried out on the binary expansions of each of the decimal values produced by the following expression for all distinct prime factors of n. That is, when 'adding' the various binary expansions of said decimal results for each p dividing n, p prime, allow that 1 + q + r + ... + s = 1, and 0 + 0 + ... + 0 = 0. Then, Sum*_{p|n} 2^(p-1) * ((2^p+1) * 2^(n-p) - 2)/(2^p - 1) + 1, when reverted to decimal, gives a(n).
a(n) -in binary, and recorded as a triangle- gives a 'Totient map' for the naturals.
                                  1
                                 11
                                101
                               1101
                              10001
                             111101
                            1000001
                           11010101
                          101001001
                         1101110101
                        10000000001
                       111101011101
                      1000000000001
                     11010111010101
                    101011001101001
                   1101010101010101
  ...

			a(p), p prime, are always 2^(p-1)+1, a result of ((2^p+1)*2^(n-p)-2)/(2^p-1)- the main parenthetical term in Sum*- being equal to 1.
a(c), c composite, is computable as follows:
a(6) = 61 because 6 has the distinct prime factors 2 and 3. So, the special summation of 2^(2-1) * ((2^2 + 1) * 2^(6-2) - 2)/(2^2 - 1) + 1 = 53, a decimal number which has a length 6 binary expansion (110101), and 2^(3-1) * ((2^3 + 1) * 2^(6-3) - 2)/(2^3 - 1) + 1 = 41, another decimal number which has a length 6 binary expansion (101001), gives Sum* =
        110101
      + 101001
       _______
        111101, which, when reverted to decimal, gives a(6).
a(12) = 3933 because 12 has the distinct prime factors 2 and 3. So, the special summation of 2^(2-1) * ((2^2 + 1) * 2^(12-2) - 2)/(2^2 - 1) + 1 = 3413, a decimal number which has a length 12 binary expansion (110101010101), and 2^(3-1) * ((2^3 + 1) * 2^(12-3) - 2)/(2^3 - 1) + 1 = 2633, another decimal number which has a length 12 binary expansion (101001001001), gives Sum* =
        110101010101
      + 101001001001
       ______________
        111101011101, which, when reverted to decimal, gives a(12).
Likewise, a(30) = 1064687485 because 30 has the distinct prime factors 2, 3, and 5. So, the special summation of 2^(2-1) * ((2^2 + 1) * 2^(30-2) - 2)/(2^2 - 1) + 1 = 894784853 = 110101010101010101010101010101 (length 30), and 2^(3-1) *((2^3 + 1) * 2^(30-3) - 2)/(2^3 - 1) + 1 = 690262601 = 101001001001001001001001001001, and 2^(5-1) * ((2^5 + 1) * 2^(30-5) - 2)/(2^5 - 1) + 1 = 571507745 = 100010000100001000010000100001,  gives Sum* =
    110101010101010101010101010101
    101001001001001001001001001001
  + 100010000100001000010000100001
    ______________________________
    111111011101011101011101111101, which, when reverted to decimal, gives a(30).

Amiram Eldar, Table of n, a(n) for n = 1..1000

Cf. A054432.

a[n_] := FromDigits[Boole@(#==1 || GCD[#,n] > 1) &/@ Range[n], 2]; Array[a, 30] (* Amiram Eldar, Mar 26 2019 *)

a(n) = my(v=vector(n, k, if (k==1, 1, gcd(k, n) != 1))); fromdigits(v, 2); \\ Michel Marcus, Mar 28 2019

More terms from Amiram Eldar, Mar 26 2019

Name clarified by Michel Marcus, Mar 28 2019

A073030 Sum_{k=1..n, gcd(n,k) = 1} 10^(k-1).

Original entry on oeis.org

1, 11, 101, 1111, 10001, 111111, 1010101, 11011011, 101000101, 1111111111, 10001010001, 111111111111, 1010100010101, 11010011001011, 101010101010101, 1111111111111111, 10001010001010001, 111111111111111111

Offset: 2

Vladeta Jovovic, Aug 15 2002

nonn

A054431 is concatenation of a(n).

Cf. A054431, A054432.

A128306 Triangle read by rows: A054521 * A007318 as infinite lower triangular matrices.

Original entry on oeis.org

1, 1, 0, 2, 1, 0, 2, 2, 1, 0, 4, 6, 4, 1, 0, 2, 4, 6, 4, 1, 0, 6, 15, 20, 15, 6, 1, 0, 4, 12, 22, 24, 16, 6, 1, 0, 6, 21, 45, 60, 51, 27, 8, 1, 0, 4, 16, 44, 76, 85, 62, 29, 8, 1, 0, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1, 0, 4, 20, 66, 144, 226, 258, 211, 120, 45, 10, 1, 0

Offset: 1

Gary W. Adamson, Feb 25 2007

Left border = phi(n), A000010: (1, 1, 2, 2, 4, 2, 6, ...). Row sums = A054432: (1, 1, 3, 5, 15, 17, 63, ...).

			First few rows of the triangle:
  1;
  1,  0;
  2,  1,  0;
  2,  2,  1,  0;
  4,  6,  4,  1,  0;
  2,  4,  6,  4,  1,  0;
  6, 15, 20, 15,  6,  1,  0;
  ...

Cf. A000010, A007318, A054432, A054521.

Definition amended and terms starting at a(56) corrected by Georg Fischer, May 29 2023

A245392 Sum_{k, k|n} 2^(k-1) + Sum_{1<=k<=n, gcd(k,n)=1} 2^(k-1).

Original entry on oeis.org

2, 4, 8, 16, 32, 56, 128, 224, 480, 856, 2048, 3200, 8192, 13656, 29920, 54752, 131072, 202104, 524288, 857952, 1939168, 3495256, 8388608, 12918016, 33013248, 55924056, 124631008, 222655840, 536870912, 809850488, 2147483648, 3579172320, 7974270688, 14316557656

Offset: 1

Michel Marcus, Jul 21 2014

nonn

The 1's in the binary expansion of 2^n - a(n) correspond to k such that 1 < gcd(k,n) < k < n. - Robert Israel, Jul 21 2014

Cf. A034729, A054432.

f:= proc(k,n) local g; g:= igcd(k,n); g = 1 or g = k end proc:
A:= n -> 1 + add(2^(k-1),k=select(f,[$1..n],n));
seq(A(n),n=1..100); # Robert Israel, Jul 21 2014

sum(k=1, n, if (gcd(k,n)==1, 2^(k-1), 0)) + sumdiv(n, k, k*2^(k-1));

a(n) = A034729(n) + A054432(n).

If p is prime a(p) = 2^p.

A338647 a(n) = Sum_{k=1..n} 2^(k/gcd(n,k) - 1).

Original entry on oeis.org

1, 2, 4, 7, 16, 22, 64, 92, 223, 342, 1024, 1132, 4096, 5462, 13534, 21937, 65536, 70978, 262144, 333472, 890590, 1398102, 4194304, 4528402, 16236031, 22369622, 57522106, 88435312, 268435456, 272976502, 1073741824, 1431677702, 3679303390, 5726623062, 16490405374, 18543422953

Offset: 1

Ilya Gutkovskiy, Apr 22 2021

nonn

Cf. A011782, A034738, A054432, A057661, A130586.

Table[Sum[2^(k/GCD[n, k] - 1), {k, 1, n}], {n, 1, 36}]

a(n) = sum(k=1, n, 2^(k/gcd(n,k) - 1)); \\ Michel Marcus, Apr 22 2021

a(n) = Sum_{d|n} A054432(d).

cp's OEIS Frontend

A306388 a(n) is a decimal number k having a length n binary expansion which encodes, from left to right at digit j, the coprimality (0) or non-coprimality (1) of j to n, for 1 < j <= n, except for the first digit, which is always 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A073030 Sum_{k=1..n, gcd(n,k) = 1} 10^(k-1).

Views

Author

Keywords

Comments

Crossrefs

A128306 Triangle read by rows: A054521 * A007318 as infinite lower triangular matrices.

Views

Author

Keywords

Comments

Examples

Crossrefs

Extensions

A245392 Sum_{k, k|n} 2^(k-1) + Sum_{1<=k<=n, gcd(k,n)=1} 2^(k-1).

Views

Author

Keywords

Comments

Crossrefs

Programs

Maple

PARI

Formula

A338647 a(n) = Sum_{k=1..n} 2^(k/gcd(n,k) - 1).

Views

Author

Keywords

Crossrefs

Programs

Mathematica

PARI

Formula