A127185 Triangle of distances between n>=1 and n>=m>=1 measured by the number of non-common prime factors.

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

Offset: 1

Author

R. J. Mathar, Mar 25 2007

Keywords

• easy
• nonn
• tabl

Comments

Consider the non-directed graph where each integer n >= 1 is a unique node labeled by n and where nodes n and m are connected if their list of exponents in their prime number decompositions n=p_1^n_1*p_2^n_2*... and m=p_1^m_1*p_2^m_2*... differs at one place p_i by 1. [So connectedness means n/m or m/n is a prime.] The distance between two nodes is defined by the number of hops on the shortest path between them. [Actually, the shortest path is not unique if the graph is not pruned to a tree by an additional convention like connecting only numbers that differ in the exponent of the largest prime factors; this does not change the distance here.] The formula says this can be computed by passing by the node of the greatest common divisor.

Examples

			T(8,10)=T(2^3,2*5)=3 as one must lower the power of p_1=2 two times and rise the power of p_3=5 once to move from 8 to 10. A shortest path is 8<->4<->2<->10 obtained by division through 2, division through 2 and multiplication by 5.
Triangle is read by rows and starts
   n\m 1 2 3 4 5 6 7 8 9 10
   ------------------------
    1| 0
    2| 1 0
    3| 1 2 0
    4| 2 1 3 0
    5| 1 2 2 3 0
    6| 2 1 1 2 3 0
    7| 1 2 2 3 2 3 0
    8| 3 2 4 1 4 3 4 0
    9| 2 3 1 4 3 2 3 5 0
   10| 2 1 3 2 1 2 3 3 4 0
		

Links

• Michael De Vlieger, Table of n, a(n) for n = 1..11325 (rows n = 1..150, flattened)
• Diego Dominici, An Arithmetic Metric, arXiv:0906.0632 [math.NT], 2009.

Crossrefs

Cf. A130836.

Programs

Mathematica

t[n_, n_] = 0; t[n_, 1] := PrimeOmega[n]; t[n_, m_] := With[{g = GCD[n, m]}, PrimeOmega[n/g] + PrimeOmega[m/g]]; Table[t[n, m], {n, 1, 14}, {m, 1, n}] // Flatten (* Jean-François Alcover, Jan 08 2014 *)

PARI

T(n, k) = my(g=gcd(n,k)); bigomega(n/g) + bigomega(k/g);
tabl(nn) = for(n=1, nn, for (k=1, n, print1(T(n, k), ", ")); print); \\ Michel Marcus, Dec 26 2018

PARI

A127185(m,n)=vecsum(abs(factor(m/n)[, 2])) \\ M. F. Hasler, Dec 07 2019

Formula

T(n,m) = A001222(n/g)+A001222(m/g) where g=gcd(n,m)=A050873(n,m).

Special cases: T(n,n)=0. T(n,1)=A001222(n).

T(m,n) = A130836(m,n) = Sum |e_k| if m/n = Product p_k^e_k. - M. F. Hasler, Dec 08 2019