A366385 -id:A366385 - cp's OEIS frontend

A196050 Number of edges in the rooted tree with Matula-Goebel number n.

0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 5, 4, 4, 5, 4, 5, 5, 5, 5, 5, 6, 5, 6, 5, 5, 6, 5, 5, 6, 5, 6, 6, 5, 5, 6, 6, 5, 6, 5, 6, 7, 6, 6, 6, 6, 7, 6, 6, 5, 7, 7, 6, 6, 6, 5, 7, 6, 6, 7, 6, 7, 7, 5, 6, 7, 7, 6, 7, 6, 6, 8, 6, 7, 7, 6, 7, 8, 6, 6, 7, 7, 6, 7, 7, 6, 8, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 6, 7, 7, 7, 8, 6, 6, 8, 6, 8

Offset: 1

Emeric Deutsch, Sep 27 2011

nonn

The Matula-Goebel number of a rooted tree is defined in the following recursive manner: to the one-vertex tree there corresponds the number 1; to a tree T with root degree 1 there corresponds the t-th prime number, where t is the Matula-Goebel number of the tree obtained from T by deleting the edge emanating from the root; to a tree T with root degree m>=2 there corresponds the product of the Matula-Goebel numbers of the m branches of T.
a(n) is, for n >= 2, the number of prime function prime(.) = A000040(.) operations in the complete reduction of n. See the W. Lang link with a list of the reductions for n = 2..100, where a curly bracket notation {.} is used for prime(.). - Wolfdieter Lang, Apr 03 2018
From Gus Wiseman, Mar 23 2019: (Start)
Every positive integer has a unique factorization (encoded by A324924) into factors q(i) = prime(i)/i, i > 0. For example:
   11 = q(1) q(2) q(3) q(5)
   50 = q(1)^3 q(2)^2 q(3)^2
  360 = q(1)^6 q(2)^3 q(3)
In this factorization, a(n) is the number of factors counted with multiplicity. For example, a(11) = 4, a(50) = 7, a(360) = 10.
(End)
From Antti Karttunen, Oct 23 2023: (Start)
Totally additive with a(prime(n)) = 1 + a(n).
Number of iterations of A366385 (or equally, of A366387) needed to reach 1.
(End)

			a(7) = 3 because the rooted tree with Matula-Goebel number 7 is the rooted tree Y.
a(2^m) = m because the rooted tree with Matula-Goebel number 2^m is the star tree with m edges.

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Emeric Deutsch, Tree statistics from Matula numbers, arXiv preprint arXiv:1111.4288 [math.CO], 2011.
F. Göbel, On a 1-1-correspondence between rooted trees and natural numbers, J. Combin. Theory, B 29 (1980), 141-143.
I. Gutman and A. Ivic, On Matula numbers, Discrete Math., 150, 1996, 131-142.
I. Gutman and Yeong-Nan Yeh, Deducing properties of trees from their Matula numbers, Publ. Inst. Math., 53 (67), 1993, 17-22.
Wolfdieter Lang, Complete prime function reduction for n = 2..100.
D. W. Matula, A natural rooted tree enumeration by prime factorization, SIAM Rev. 10 (1968) 273.
Index entries for sequences related to Matula-Goebel numbers

One less than A061775.
Cf. A000040, A000081, A000720, A003963, A007097, A020639, A049084, A109082, A109129, A317713, A318995, A358729.
Cf. A324850, A324922, A324923, A324924, A324925, A324931, A324935, A366385, A366387, A366388.

import Data.List (genericIndex)
a196050 n = genericIndex a196050_list (n - 1)
a196050_list = 0 : g 2 where
   g x = y : g (x + 1) where
     y = if t > 0 then a196050 t + 1 else a196050 r + a196050 s
         where t = a049084 x; r = a020639 x; s = x `div` r
-- Reinhard Zumkeller, Sep 03 2013

with(numtheory): a := proc (n) local r, s: r := proc (n) options operator, arrow: op(1, factorset(n)) end proc: s := proc (n) options operator, arrow: n/r(n) end proc: if n = 1 then 0 elif bigomega(n) = 1 then 1+a(pi(n)) else a(r(n))+a(s(n)) end if end proc: seq(a(n), n = 1 .. 110);

a[1] = 0; a[n_?PrimeQ] := a[n] = 1 + a[PrimePi[n]]; a[n_] := Total[#[[2]] * a[#[[1]] ]& /@ FactorInteger[n]];
Array[a, 110] (* Jean-François Alcover, Nov 16 2017 *)
difac[n_]:=If[n==1,{},With[{i=PrimePi[FactorInteger[n][[1,1]]]},Sort[Prepend[difac[n*i/Prime[i]],i]]]];
Table[Length[difac[n]],{n,100}] (* Gus Wiseman, Mar 23 2019 *)

a(n) = my(f=factor(n)); [self()(primepi(p))+1 |p<-f[,1]]*f[,2]; \\ Kevin Ryde, May 28 2021

from functools import lru_cache
from sympy import isprime, primepi, factorint
@lru_cache(maxsize=None)
def A196050(n):
    if n == 1 : return 0
    if isprime(n): return 1+A196050(primepi(n))
    return sum(e*A196050(p) for p, e in factorint(n).items()) # Chai Wah Wu, Mar 19 2022

a(1)=0; if n = prime(t) (the t-th prime), then a(n)=1 + a(t); if n = r*s (r,s>=2), then a(n)=a(r)+a(s). The Maple program is based on this recursive formula.
a(n) = A061775(n) - 1.
a(n) = A109129(n) + A366388(n) = A109082(n) + A358729(n). - Antti Karttunen, Oct 23 2023

A324923 Number of distinct factors in the factorization of n into factors q(i) = prime(i)/i, i > 0.

Original entry on oeis.org

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

Offset: 1

Gus Wiseman, Mar 20 2019

nonn

Also the number of distinct proper terminal subtrees of the rooted tree with Matula-Goebel number n. See illustrations in A061773.

			The factorization 22 = q(1)^2 q(2) q(3) q(5) has four distinct factors, so a(22) = 4.

One less than A317713.
Cf. A000081, A003963, A061773, A061775, A109082, A109129, A120383, A196050.
Cf. A324850, A324922, A324924, A324925, A324931, A324934, A324935, A324936, A366385, A366386.

difac[n_]:=If[n==1,{},With[{i=PrimePi[FactorInteger[n][[1,1]]]},Sort[Prepend[difac[n*i/Prime[i]],i]]]];
Table[Length[Union[difac[n]]],{n,100}]

A006530(n) = if(1==n, n, my(f=factor(n)); f[#f~, 1]);
A324923(n) = { my(lista = List([]), gpf, i); while(n > 1, gpf=A006530(n); i = primepi(gpf); n /= gpf; n *= i; listput(lista,i)); #Set(lista); }; \\ Antti Karttunen, Oct 23 2023

a(n) = A317713(n) - 1.

a(n) = A196050(n) - A366386(n). - Antti Karttunen, Oct 23 2023

Data section extended up to a(108) by Antti Karttunen, Oct 23 2023

A366388 The number of edges minus the number of leafs in the rooted tree with Matula-Goebel number n.

Original entry on oeis.org

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

Offset: 1

Antti Karttunen, Oct 23 2023

nonn

Number of iterations of A366385 needed to reach the nearest power of 2.

			See illustrations in A061773.

Cf. A000720, A006530, A052126, A061395, A061773, A366385.
Cf. A109129 (gives the exponent of the nearest power of 2 reached), A196050 (distance to the farthest power of 2, which is 1).
Cf. also A329697, A331410.

Array[-1 + Length@ NestWhileList[PrimePi[#2]*#1/#2 & @@ {#, FactorInteger[#][[-1, 1]]} &, #, ! IntegerQ@ Log2[#] &] &, 105] (* Michael De Vlieger, Oct 23 2023 *)

A366388(n) = if(n<=2, 0, if(isprime(n), 1+A366388(primepi(n)), my(f=factor(n)); (apply(A366388, f[, 1])~ * f[, 2])));

A006530(n) = if(1==n, n, my(f=factor(n)); f[#f~, 1]);
A366385(n) = { my(gpf=A006530(n)); primepi(gpf)*(n/gpf); };
A366388(n) = if(n && !bitand(n,n-1),0,1+A366388(A366385(n)));

Totally additive with a(2) = 0, and for n > 1, a(prime(n)) = 1 + a(n).
a(n) = A196050(n) - A109129(n).
a(2n) = a(A000265(n)) = a(n).

A366387 Divide n by its smallest prime factor, then multiply with the index of that same prime; a(1) = 0 by convention.

Original entry on oeis.org

0, 1, 2, 2, 3, 3, 4, 4, 6, 5, 5, 6, 6, 7, 10, 8, 7, 9, 8, 10, 14, 11, 9, 12, 15, 13, 18, 14, 10, 15, 11, 16, 22, 17, 21, 18, 12, 19, 26, 20, 13, 21, 14, 22, 30, 23, 15, 24, 28, 25, 34, 26, 16, 27, 33, 28, 38, 29, 17, 30, 18, 31, 42, 32, 39, 33, 19, 34, 46, 35, 20, 36, 21, 37, 50, 38, 44, 39, 22, 40, 54, 41, 23, 42, 51

Offset: 1

Antti Karttunen, Oct 23 2023

nonn

Cf. A000720, A020639, A032742, A055396.
Cf. A196050 (number of iterations needed to reach 1), A324923.
Cf. also A366385, and A060681 (divide by the smallest prime p, then multiply with p-1),

Array[PrimePi[#2]*#1/#2 & @@ {#, FactorInteger[#][[1, 1]]} &, 85] (* Michael De Vlieger, Oct 23 2023 *)

A020639(n) = if(1==n,n,vecmin(factor(n)[, 1]));
A366387(n) = { my(spf=A020639(n)); primepi(spf)*(n/spf); };

a(n) = A032742(n) * A055396(n) = (n/A020639(n)) * A000720(A020639(n)).

a(2n) = n, a(3*(2n+1)) = 2*(2n+1) = 4n + 2.

cp's OEIS Frontend

A196050 Number of edges in the rooted tree with Matula-Goebel number n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

A324923 Number of distinct factors in the factorization of n into factors q(i) = prime(i)/i, i > 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A366388 The number of edges minus the number of leafs in the rooted tree with Matula-Goebel number n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

A366387 Divide n by its smallest prime factor, then multiply with the index of that same prime; a(1) = 0 by convention.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula