|
%I #25 Oct 10 2023 16:59:51
%S 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,
%T 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,
%U 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
%N Triangle of distances between n>=1 and n>=m>=1 measured by the number of non-common prime factors.
%C 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.
%H Michael De Vlieger, <a href="/A127185/b127185.txt">Table of n, a(n) for n = 1..11325</a> (rows n = 1..150, flattened)
%H Diego Dominici, <a href="http://arxiv.org/abs/0906.0632">An Arithmetic Metric</a>, arXiv:0906.0632 [math.NT], 2009.
%F T(n,m) = A001222(n/g)+A001222(m/g) where g=gcd(n,m)=A050873(n,m).
%F Special cases: T(n,n)=0. T(n,1)=A001222(n).
%F T(m,n) = A130836(m,n) = Sum |e_k| if m/n = Product p_k^e_k. - _M. F. Hasler_, Dec 08 2019
%e 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.
%e Triangle is read by rows and starts
%e n\m 1 2 3 4 5 6 7 8 9 10
%e ------------------------
%e 1| 0
%e 2| 1 0
%e 3| 1 2 0
%e 4| 2 1 3 0
%e 5| 1 2 2 3 0
%e 6| 2 1 1 2 3 0
%e 7| 1 2 2 3 2 3 0
%e 8| 3 2 4 1 4 3 4 0
%e 9| 2 3 1 4 3 2 3 5 0
%e 10| 2 1 3 2 1 2 3 3 4 0
%t 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 *)
%o (PARI) T(n, k) = my(g=gcd(n,k)); bigomega(n/g) + bigomega(k/g);
%o tabl(nn) = for(n=1, nn, for (k=1, n, print1(T(n, k), ", ")); print); \\ _Michel Marcus_, Dec 26 2018
%o (PARI) A127185(m,n)=vecsum(abs(factor(m/n)[, 2])) \\ _M. F. Hasler_, Dec 07 2019
%Y Cf. A130836.
%K easy,nonn,tabl
%O 1,5
%A _R. J. Mathar_, Mar 25 2007
|
