Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 DivisorHasseDiagram

Source Notebook

Generate a transitive reduction graph for the divisors of a positive integer

Contributed by: Shenghui Yang (Wolfram Research)

ResourceFunction["DivisorHasseDiagram"][n]

gives a Hasse diagram based on the divisors of n, represented as a Graph.

Details and Options

A Hasse diagram is a directed graph representing a poset, with edges drawn based on the partial ordering. ResourceFunction["DivisorHasseDiagram"] uses the divisors as the graph's vertices and divisibility as the partial ordering.
ResourceFunction["DivisorHasseDiagram"] takes the same options as Graph.
ResourceFunction["DivisorHasseDiagram"] is efficient due to the slow growth of the Divisors function in length. So it does not suffer from the general NP-hardness of generating a directed TransitiveReductionGraph.

Examples

Basic Examples (2) 

The Hasse diagram for the divisors of 12:

In[1]:=
ResourceFunction["DivisorHasseDiagram"][12]
Out[1]=
In[2]:=
Divisors[12]
Out[2]=

The Hasse diagram for a prime number:

In[3]:=
ResourceFunction["DivisorHasseDiagram"][7]
Out[3]=

Properties and Relations (2) 

For any prime power, DivisorHasseDiagram gives a linear graph where the number of vertices is one more than the exponent of the prime power:

In[4]:=
TableForm[ ResourceFunction["DivisorHasseDiagram"][#, VertexLabels -> "Name"] & /@ (7^Range[2, 5])]
Out[4]=

The number of edges grows very slowly:

In[5]:=
ListPlot[EdgeCount[ResourceFunction["DivisorHasseDiagram"][#]] & /@ Range[2, 500], Filling -> Bottom]
Out[5]=

Neat Examples (3) 

Hasse diagrams for some abundant numbers (3) 

720 is an abundant number:

In[6]:=
ResourceFunction["AbundantNumberQ"][720]
Out[6]=

Generate the Hasse diagram:

In[7]:=
ResourceFunction["DivisorHasseDiagram"][720, PlotTheme -> "LargeNetworkDefault", VertexLabels -> "Name"]
Out[7]=

2520 is an abundant number:

In[8]:=
ResourceFunction["AbundantNumberQ"][2520]
Out[8]=

Generate the Hasse diagram:

In[9]:=
ResourceFunction["DivisorHasseDiagram"][2520, PlotTheme -> "LargeNetworkDefault", VertexLabels -> Placed["Name", Tooltip]]
Out[9]=

21621600 is the only abundant number n that achieves equality in the inequality , where d(n) is DivisorSigma[0,n] (the inequality was discovered by J.K. Nicolas):

In[10]:=
ResourceFunction["DivisorHasseDiagram"][21621600, PlotTheme -> "LargeNetworkDefault"]
Out[10]=

Publisher

Shenghui Yang

Version History

  • 1.0.0 – 27 May 2021

Source Metadata

  • Citation:
    • Nicolas, J.L., Robin, G., "Majorations Explicites Pour le Nombre de Diviseurs de N. Canad. Math. Bull., vol. 26, no. 4, 485–492, 1983. DOI: 10.4153/CMB-1983-078-5

Related Resources

License Information