|
| |
|
|
A127185
|
|
Triangle of distances between n>=1 and 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; 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.
|
|
|
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).
|
|
|
EXAMPLE
| 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
---------------------
.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.
|
|
|
CROSSREFS
| Sequence in context: A125939 A125942 A061986 * A159780 A138036 A055136
Adjacent sequences: A127182 A127183 A127184 * A127186 A127187 A127188
|
|
|
KEYWORD
| easy,nonn,tabl
|
|
|
AUTHOR
| R. J. Mathar (mathar(AT)strw.leidenuniv.nl), Mar 25 2007
|
| |
|
|
