|
| |
|
|
A127185
|
|
Triangle of distances between n>=1 and n>=m>=1 measured by the number of non-common prime factors.
|
|
5
|
|
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,5
|
|
|
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.
|
|
|
LINKS
|
|
|
|
FORMULA
|
Special cases: T(n,n)=0. T(n,1)=A001222(n).
|
|
|
EXAMPLE
|
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
|
|
|
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 *)
|
|
|
PROG
|
(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
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
