A038566 -id:A038566 - cp's OEIS frontend

A381497 a(n) = sum of numbers k < n such that 1 < gcd(k,n) and rad(k) != rad(n), where rad = A007947.

0, 0, 0, 0, 0, 9, 0, 6, 6, 25, 0, 36, 0, 49, 45, 42, 0, 81, 0, 100, 84, 121, 0, 144, 45, 169, 96, 196, 0, 315, 0, 210, 198, 289, 175, 354, 0, 361, 273, 430, 0, 609, 0, 484, 435, 529, 0, 648, 140, 655, 459, 676, 0, 801, 385, 826, 570, 841, 0, 1260, 0, 961, 798

Offset: 1

Michael De Vlieger, Mar 02 2025

nonn

Analogous to A066760(n), the sum of row n of A133995, and A381499(n), sum of row n of A272619.

			Table of n and a(n) for select n, showing prime power decomposition of both and row n of A381094:
   n   Factor(n) a(n)  Factor(a(n))  Row n of A381094
  -------------------------------------------------------------------
   6   2 * 3       9   3^2           {2,3,4}
   8   2^3         6   2 * 3         {6}
   9   3^2         6   2 * 3         {6}
  10   2 * 5      25   5^2           {2,4,5,6,8}
  12   2^2 * 3    36   2^2 * 3^2     {2,3,4,8,9,10}
  14   2 * 7      49   7^2           {2,4,6,7,8,10,12}
  15   3 * 5      45   3^2 * 5       {3,5,6,9,10,12}
  16   2^4        42   2 * 3 * 7     {6,10,12,14}
  18   2 * 3^2    81   3^4           {2,3,4,8,9,10,14,15,16}
  20   2^2 * 5   100   2^2 * 5^2     {2,4,5,6,8,12,14,15,16,18}
  21   3 * 7      84   2^2 * 3 * 7   {3,6,7,9,12,14,15,18}
  22   2 * 11    121   11^2          {2,4,6,8,10,11,12,14,16,18,20}
  24   2^3 * 3   144   2^4 * 3^2     {2,3,4,8,9,10,14,15,16,20,21,22}
a(6) = (2+4) + (3) = 9,
a(n) = 6 for n in {8, 9} since 6 is the only number less than n that shares a factor with n but does not have the same squarefree kernel as n.
a(10) = (2+4+6+8) + (5) = 25.
a(12) = (2+4+8+10) + (3+9) = 36.
a(14) = (2+4+6+8+10+12) + (7) = 49.
a(15) = (3+6+9+12) + (5+10) = 45.
a(16) = (6+10+12+14) = 42, etc.

Michael De Vlieger, Table of n, a(n) for n = 1..16384
Michael De Vlieger, Log log scatterplot of a(n), n = 6..2^14, ignoring a(n) = 0, showing a(n) for prime power n in gold, a(n) for squarefree n in green, otherwise blue.

Cf. A007947, A038566, A066760, A067392, A121998, A369609, A381094, A381096, A381498, A381499.

rad[x_] := rad[x] = Times @@ FactorInteger[x][[All, 1]]; Table[r = rad[n]; Total@ Select[Range[n], Nor[CoprimeQ[#, n], rad[#] == r] &], {n, 120}]

a(n) is the sum of row n of A381094.
a(n) = 0 for prime n and n = 4.
a(n) = A067392(n) - A381498(n).

A124224 Table T(n,k) = reciprocal of k-th number prime to n, modulo n, for 1 <= k <= phi(n).

Original entry on oeis.org

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

Offset: 1

Franklin T. Adams-Watters, Oct 20 2006

T(n,k) = smallest m such that A038566(n,k) * m = 1 (mod n).

For n>1 every row begins with 1 and ends with n-1. T(n,k) = A038566(n,k)^(phi(n) - 1) (mod n). - Geoffrey Critzer, Jan 03 2015

			The table T(n,k) starts:
n\k 1  2  2  3 4  5 6  7 8  9 10 11
1:  0
2:  1
3:  1  2
4:  1  3
5:  1  3  2  4
6:  1  5
7:  1  4  5  2 3  6
8:  1  3  5  7
9:  1  5  7  2 4  8
10: 1  7  3  9
11: 1  6  4  3 9  2 8  7 5 10
12: 1  5  7 11
13: 1  7  9 10 8 11 2  5 3  4  6 12
14: 1  5  3 11 9 13
15: 1  8  4 13 2 11 7 14
16: 1 11 13  7 9  3 5 15
...
n = 17: 1  9  6 13 7  3  5 15 2 12 14 10 4 11 8 16,
n = 18: 1 11 13  5 7 17,
n = 19: 1 10 13  5 4 16 11 12 17 2 7 8 3 15 14 6 9 18,
n = 20: 1 7 3 9 11 17 13 19.
... reformatted (extended and corrected), - _Wolfdieter Lang_, Oct 06 2016

Robert Israel, Table of n, a(n) for n = 1..10060
Eric Weisstein's World of Mathematics, Modular Inverse

Cf. A124223, A102057, A038566, A000010 (row lengths), A023896 (row sums after first)

0,seq(seq(i^(-1) mod m, i = select(t->igcd(t,m)=1, [$1..m-1])),m=1..100); # Robert Israel, May 18 2014

Table[nn = n; a = Select[Range[nn], CoprimeQ[#, nn] &];
PowerMod[a, -1, nn], {n, 1, 20}] // Grid (* Geoffrey Critzer, Jan 03 2015 *)

T(n,k) * A038566(n,k) = 1 (mod n), for n >=1 and k=1..A000010(n). - Wolfdieter Lang, Oct 06 2016

A141295 Largest m<=n such that all k with 1<=k<=m are divisors of n or coprime to n.

Original entry on oeis.org

1, 2, 3, 4, 5, 3, 7, 5, 5, 3, 11, 7, 13, 3, 5, 5, 17, 3, 19, 5, 5, 3, 23, 8, 9, 3, 5, 5, 29, 3, 31, 5, 5, 3, 9, 7, 37, 3, 5, 5, 41, 3, 43, 5, 5, 3, 47, 8, 13, 3, 5, 5, 53, 3, 9, 5, 5, 3, 59, 7, 61, 3, 5, 5, 9, 3, 67, 5, 5, 3, 71, 9, 73, 3, 5, 5, 13, 3, 79, 5, 5, 3, 83, 7, 9, 3, 5, 5, 89, 3, 13, 5, 5, 3

Offset: 1

Reinhard Zumkeller, Jun 23 2008

nonn

n mod a(n) = 0 or GCD(n,a(n)) = 1;
a(n) = n iff n=1 or n=4 or n is prime; a(A046022(n))=A046022(n);
a(p^2) = 2*p - 1 for odd primes p.

R. Zumkeller, Table of n, a(n) for n = 1..10000

Cf. A027750, A038566, A076274.

A164296 Let S(n) be the set of all positive integers that are <= n and are coprime to n. a(n) = the number of members of S(n) that are each coprime to every other member of S(n).

Original entry on oeis.org

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

Offset: 1

Leroy Quet, Aug 12 2009

nonn

A164296(n) + A164297(n) = phi(n) (= A000010(n) = the number of elements in S(n)).

			The positive integers that are <= 9 and are coprime to 9 are: 1,2,4,5, 7,8. 1 is coprime to each other member in S(9). While 2, 4, and 8 are non-coprime to each other. 5 is coprime to each other member of S(9). And 7 is also coprime to each other member. Since there are 3 integers in S(9) that are coprime to each other member -- these integers being 1, 5, and 7 -- then a(9) = 3.

Reinhard Zumkeller, Table of n, a(n) for n = 1..1000

Cf. A164297.

Cf. A038566, A000010.

import Data.List ((\\))
a164296 n = length [m | let ts = a038566_row n, m <- ts,
                        all ((== 1) . gcd m) (ts \\ [m])]
-- Reinhard Zumkeller, May 28 2015

Extended by Ray Chandler, Mar 16 2010

A164297 Let S(n) be the set of all positive integers that are <= n and are coprime to n. a(n) = the number of members of S(n) that are each non-coprime with at least one other member of S(n).

Original entry on oeis.org

0, 0, 0, 0, 2, 0, 4, 0, 3, 2, 8, 0, 9, 2, 5, 4, 13, 0, 14, 2, 7, 6, 18, 0, 15, 7, 14, 6, 24, 0, 25, 8, 14, 10, 19, 4, 31, 11, 19, 9, 35, 2, 36, 11, 17, 14, 40, 4, 35, 10, 25, 15, 45, 5, 32, 14, 28, 20, 51, 2, 52, 20, 28, 21, 40, 7, 58, 20, 35, 13, 61, 9, 62, 24, 30, 23, 50, 8, 68, 18, 43, 27

Offset: 1

Leroy Quet, Aug 12 2009

nonn

A164296(n) + A164297(n) = phi(n) (= A000010(n) = the number of elements in S(n)).

			The positive integers that are <= 9 and are coprime to 9 are: 1,2,4,5, 7,8. 1 is coprime to each other member in S(9). While 2, 4, and 8 are non-coprime to each other. 5 is coprime to each other member of S(9). And 7 is also coprime to each other member. Since there are 3 integers in S(9) that are each non-coprime with at least one other member of S(9) -- these integers being 2, 4, and 8 -- then a(9) = 3.

Reinhard Zumkeller, Table of n, a(n) for n = 1..1000

Cf. A164296, A036997, A048597.

Cf. A038566, A000010.

import Data.List ((\\))
a164297 n = length [m | let ts = a038566_row n, m <- ts,
                        any ((> 1) . gcd m) (ts \\ [m])]
-- Reinhard Zumkeller, May 28 2015

Extended by Ray Chandler, Mar 16 2010

A282601 a(n) = Sum_(k=1..phi(n)/2) floor(d_k/2) where d_k are the totatives of n.

Original entry on oeis.org

0, 0, 0, 0, 1, 0, 2, 1, 3, 1, 6, 2, 9, 3, 6, 6, 16, 5, 20, 8, 14, 10, 30, 10, 29, 15, 28, 18, 49, 14, 56, 28, 38, 28, 48, 24, 81, 36, 54, 36, 100, 30, 110, 50, 64, 55, 132, 44, 124, 57, 96, 72, 169, 56, 130, 78, 122, 91, 210, 56, 225, 105, 136, 120, 186, 80, 272, 128, 182, 102

Offset: 1

Michel Marcus, Feb 19 2017

nonn

The totatives of n are the numbers k <= n with gcd(k,n) = 1.

David Zmiaikou, Origamis and permutation groups, Thesis, 2011. See p. 65.

Cf. A000010, A023896, A038566, A066840, A282600.

a(n) = {vn = vector(n, k, k); vt = select(x->(gcd(x,n) == 1), vn); sum(k=1, #vt\2, vt[k]\2);}

A319513 The boustrophedonic Rosenberg-Strong function maps N onto N X N where N = {0, 1, 2, ...} and n -> factor(a(n)) = 2^x*3^y -> (x, y).

Original entry on oeis.org

1, 3, 6, 2, 4, 12, 36, 18, 9, 27, 54, 108, 216, 72, 24, 8, 16, 48, 144, 432, 1296, 648, 324, 162, 81, 243, 486, 972, 1944, 3888, 7776, 2592, 864, 288, 96, 32, 64, 192, 576, 1728, 5184, 15552, 46656, 23328, 11664, 5832, 2916, 1458, 729, 2187, 4374, 8748, 17496

Offset: 0

Peter Luschny, Sep 21 2018

nonn

If (x, y) and (x', y') are adjacent points on the trajectory of the map then for the boustrophedonic Rosenberg-Strong function max(|x - x'|, |y - y'|) is always 1 whereas for the Rosenberg-Strong function this quantity can become arbitrarily large. In this sense the boustrophedonic variant is continuous in contrast to the original Rosenberg-Strong function.

A. L. Rosenberg, H. R. Strong, Addressing arrays by shells, IBM Technical Disclosure Bulletin, vol 14(10), 1972, p. 3026-3028.

Georg Cantor, Ein Beitrag zur Mannigfaltigkeitslehre, Journal für die reine und angewandte Mathematik 84 (1878), 242-258.
Steven Pigeon, Mœud deux, 2018.
A. L. Rosenberg, Allocating storage for extendible Arrays, J. ACM, vol 21(4), 1974, p. 652-670.
M. P. Szudzik, The Rosenberg-Strong Pairing Function", arXiv:1706.04129 [cs.DM], 2017.

See A319514 for a non-decoded variant with interleaved x and y coordinates.

Cf. A038566/A038567, A157807/A157813.

function bRS(n)
    m = x = isqrt(n)
    y = n - x^2
    x <= y && ((x, y) = (2x - y, x))
    isodd(m) ? (y, x) : (x, y)
end
A319513(n) = ((x, y) = bRS(n); 2^x * 3^y)
[A319513(n) for n in 0:52] |> println

A319513 := proc(n) local b, r, p, m;
    b := floor(sqrt(n)); r := n - b^2;
    p := `if`(r < b, [b, r], [2*b-r, b]);
    m := `if`(p[1] > p[2], p[1], p[2]);
    `if`(irem(m,2) = 0, 2^p[1]*3^p[2], 2^p[2]*3^p[1]) end:
seq(A319513(n), n=0..52);

a[n_] := Module[{b, r, p1, p2, m}, b = Floor[Sqrt[n]]; r = n-b^2; {p1, p2} = If[rp2, p1, p2]; If[EvenQ[m], 2^p1 3^p2, 2^p2 3^p1]]; Table[a[n], {n, 0, 52}] (* Jean-François Alcover, Feb 14 2019, from Maple *)

A322144 a(n) = Sum_{i=1..phi(n)-1} (r(i+1)-r(i))^2 where r(1) = 1 < ... < n-1 = r(phi(n)) are the phi(n) integers relatively prime to n.

Original entry on oeis.org

0, 0, 1, 4, 3, 16, 5, 12, 11, 24, 9, 36, 11, 32, 29, 28, 15, 56, 17, 52, 39, 48, 21, 76, 31, 56, 41, 68, 27, 128, 29, 60, 59, 72, 57, 116, 35, 80, 69, 108, 39, 168, 41, 100, 95, 96, 45, 156, 59, 136, 89, 116, 51, 176, 85, 140, 99, 120, 57, 260, 59, 128, 125, 124, 99

Offset: 1

Michel Marcus, Nov 28 2018

nonn

			a(1) and a(2) are 0, since we have an empty sum.
For a(3), the integers < 3, coprime to 3, are 1 and 2, so a(3) = (2-1)^2 = 1.

David A. Corneth, Table of n, a(n) for n = 1..10000
Paul Erdos, Some Unconventional Problems in Number Theory, Mathematics Magazine, Vol. 52, No. 2, Mar., 1979, pp. 67-70. See Problem 12. p. 70.

Cf. A000010 (phi), A038566 (rows of r).

Cf. A040976 (prime(n)-2), A132952 (isolated totatives).

a[n_] := Total[Differences[Select[Range[n], GCD[n,#]==1 &]]^2]; Array[a, 50] (* Amiram Eldar, Nov 28 2018 *)

a(n) = {v = select(x->gcd(x,n)==1, vector(n, k, k)); sum(i=1, #v-1, (v[i+1] - v[i])^2);}

a(n) = {my(res = 0, io = 1, in = 2); while(in < n, while(gcd(in, n) > 1, in++); res += (in - io)^2; io = in; in++); res}
first(n) = {my(res = vector(n)); for(i = 1, n, c = factorback(factor(i)[, 1]); if(c == i, res[i] = a(i), res[i] = res[c] * (i / c) + 4 * (i / c - 1))); res } \\ David A. Corneth, Nov 28 2018

a(p) = p-2, for p prime.

a(k^2 * m) = k * a(k * m) + 4 * (k - 1). - David A. Corneth, Nov 28 2018

A322936 Triangular array in which the n-th row lists the numbers strongly prime to n (in ascending order). For the empty rows n = 2, 3, 4 and 6 we set by convention 0.

Original entry on oeis.org

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

Offset: 1

Peter Luschny, Apr 01 2019

a is strongly prime to n if and only if a <= n is prime to n and a does not divide n-1. See the link to 'Strong Coprimality'. (Our terminology follows the plea of Knuth, Graham and Patashnik in Concrete Mathematics, p. 115.)

			The length of row n is A181830(n) = phi(n) - tau(n-1). The triangular array starts:
[1] {1}
[2] {}
[3] {}
[4] {}
[5] {3}
[6] {}
[7] {4, 5}
[8] {3, 5}
[9] {5, 7}
[11] {3, 4, 6, 7, 8, 9}
[12] {5, 7}
[10] {7}
[13] {5, 7, 8, 9, 10, 11}
[14] {3, 5, 9, 11}
[15] {4, 8, 11, 13}
[16] {7, 9, 11, 13}
[17] {3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15}
[18] {5, 7, 11, 13}
[19] {4, 5, 7, 8, 10, 11, 12, 13, 14, 15, 16, 17}
[20] {3, 7, 9, 11, 13, 17}

Peter Luschny, Strong Coprimality

Cf. A000010, A038566, A181831, A181832, A181833, A181834, A181835, A181836, A322937.

StrongCoprimes := n -> select(k -> igcd(k, n)=1, {$1..n}) minus numtheory:-divisors(n-1):
A322936row:=  proc(n) if n in {2, 3, 4, 6} then return 0 else op(StrongCoprimes(n)) fi end:
seq(A322936row(n), n=1..20);

Table[If[n == 1, {1}, Select[Range[2, n], And[GCD[#, n] == 1, Mod[n - 1, #] != 0] &] /. {} -> {0}], {n, 21}] // Flatten (* Michael De Vlieger, Apr 01 2019 *)

def primeto(n):
    return [p for p in range(n) if gcd(p, n) == 1]
def strongly_primeto(n):
    return [p for p in set(primeto(n)) - set((n-1).divisors())]
def A322936row(n):
    if n == 1: return [1]
    if n in [2, 3, 4, 6]: return [0]
    return sorted(strongly_primeto(n))
for n in (1..21): print(A322936row(n))

A332436 The number of even numbers <= n of the smallest nonnegative reduced residue system modulo 2*n + 1, for n >= 0.

Original entry on oeis.org

1, 0, 1, 1, 2, 2, 3, 2, 4, 4, 4, 5, 5, 4, 7, 7, 6, 6, 9, 6, 10, 10, 6, 11, 11, 8, 13, 10, 10, 14, 15, 8, 12, 16, 12, 17, 18, 10, 16, 19, 14, 20, 16, 14, 22, 18, 16, 18, 24, 14, 25, 25, 12, 26, 27, 18, 28, 22, 18, 24, 28, 20, 25, 31, 22, 32, 28, 18, 34, 34, 24

Offset: 0

Wolfdieter Lang, Feb 29 2020

For the smallest positive reduced residue system modulo N see the array A038566. Here the nonnegative residue system [0, 1, ..., N-1] is considered, differing only for N = 1 from A038566, with [0] (instead of [1]).
This sequence gives the complement of A332435 (with 0 for n = 0 included) relative to the number of positive numbers <= n of the smallest nonnegative reduced residue system modulo (2*n+1). Thus a(n) + A332435(n) = phi(n)/2, for n >= 1, with phi = A000010. For n = 0 one has 1 + 0 = 1.
a(n) gives also the number of even numbers appearing in the complete modified doubling sequence system (name it MDS(b)), for b = 2*n + 1, with n >= 1, proposed in a comment from Gary W. Adamson, Aug 24 2019, in the example section of A135303 for prime b.

			n = 4, b = 9: the even numbers <= 4 in RRS(9) := [1, 2, 4, 5, 7, 8] are {2, 4}, hence a(4) = 2.
The complete MDS(9) system has one cycles of length 3: Cy*(9, 1) = (2, 4, 1), with the even numbers {2, 4}.
n = 8, b = 17: the even numbers <= 8 in RRS(17) := [1, 2, ..., 16] are {2, 4, 6 ,8}, hence a(8) = 4.
The complete MDS(17) system has two cycles of length 4: Cy*(17, 1) = (2, 4, 8, 1) and Cy*(17, 2) = (6, 5, 7, 3) and the even numbers are {2, 4, 6 ,8}.

Cf. A000010, A038566, A135303, A332435.

a(n) = A000010(n)/2 - A332435(n), for n >= 1, and a(0) = 1.

cp's OEIS Frontend

A381497 a(n) = sum of numbers k < n such that 1 < gcd(k,n) and rad(k) != rad(n), where rad = A007947.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A124224 Table T(n,k) = reciprocal of k-th number prime to n, modulo n, for 1 <= k <= phi(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A141295 Largest m<=n such that all k with 1<=k<=m are divisors of n or coprime to n.

Views

Author

Keywords

Comments

Links

Crossrefs

A164296 Let S(n) be the set of all positive integers that are <= n and are coprime to n. a(n) = the number of members of S(n) that are each coprime to every other member of S(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Extensions

A164297 Let S(n) be the set of all positive integers that are <= n and are coprime to n. a(n) = the number of members of S(n) that are each non-coprime with at least one other member of S(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Extensions

A282601 a(n) = Sum_(k=1..phi(n)/2) floor(d_k/2) where d_k are the totatives of n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

A319513 The boustrophedonic Rosenberg-Strong function maps N onto N X N where N = {0, 1, 2, ...} and n -> factor(a(n)) = 2^x*3^y -> (x, y).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Julia

Maple

Mathematica

A322144 a(n) = Sum_{i=1..phi(n)-1} (r(i+1)-r(i))^2 where r(1) = 1 < ... < n-1 = r(phi(n)) are the phi(n) integers relatively prime to n.

Views

Author

Keywords

Examples

Links