When choosing rows = 4000 and columns = 546, an interesting pattern emerges.
For all integers n ≥ 0, the ranges [243 + (n * 546)] to [249 + (n * 546)] inclusive appear to contain no prime numbers. Same with the ranges [297 + (n * 546)] to [303 + (n * 546)].
For both sets of ranges, the minimum gap between the closest neighbouring primes appears to be at least 10 (in decimal). Does anyone know of a number-theoretic explanation for this kind of pattern?
The term 'hallucinations' is by now a common expression when speaking about the shortcomings of LLMs and Generative AI. However, I propose that the expression is misdirected at LLMs and takes away rather than adds to our understanding of the underlying issue.
It is humans who hallucinate when they expect an answer from an LLM that is 'truthful' or 'right' or 'correct'. The LLMs (as of June 2024) have no concept or understanding of truth, falsehood, right, wrong, correct or incorrect. Rather, when people claim that LLMs hallucinate, the LLMs are in fact generating responses and performing exactly as they are programmed to do.
However, humans should be forgiven for their hallucinations, because the interaction with the LLMs and the generated results are often designed by their makers to precisely give this unfortunate impression. Indeed, it is the unreasonable effectiveness of LLMs in the natural language domain and their successful application to many diverse tasks, that 'hallucinations' are now seen as the most serious defect of LLMs.
The virtue of courage is a habitual strength of the will that enables its possessor to be ready to suffer for a good cause. Excess of this strength is foolhardiness; its defect is cowardice.
In a similar fashion, we all have a natural desire to know, the pursuit of knowledge is good in and of itself. However its defect is negligence, and its excess is curiositas.
This article examines curiositas and its corresponding virtue studiositas. Although it is framed in the context of a Christian viewpoint, it may offer insights to people from all faith backgrounds or from a non-faith perspective.
I gave my good faith understanding of what a tree is, but your comment made me think more about it, and to look it up.
From chapter two of the book "Algorithmic Graph Theory and Sage" [1]; it states the following concerning directedness:
"A directed tree is a digraph which would be a tree if the directions on the edges
were ignored." ... which is the correct definition from my understanding.
However, the authors go on to say:
"A rooted tree can be regarded as a directed tree since...Directed trees are pervasive in theoretical computer science, as they are useful structures for describing algorithms and relationships between objects in certain datasets."
So, colloquially (but perhaps not formally), one can refer to a directed, rooted, connected, acyclic graph as a tree.
Concerning weights, wolfram provides a definition of a strict graph [2] which specifies the unweighted qualifier (and undirected qualifier):
"A simple graph, also called a strict graph (Tutte 1998, p. 2), is an unweighted, undirected graph..."
The wolfram definition of a tree [3] includes the 'simple' qualifier:
Tree "is a simple, undirected, connected, acyclic graph..."
So, I would suggest formally, a tree cannot have weights (recall that weights are basically labels assigned to the edges).
Incidentally, I took down from the shelf my copy of The Art of Computer Programming (TAOCP) Volume One, and section 2.3 deals with trees exclusively. Donal Knuth asserts that trees are 'the most important nonlinear structures that arise in computer algorithms'. I skimmed the entire section and although he makes reference to weighted path lengths, I did not see any mention of weighted trees.
So, to my understanding, the original definition I proposed is valid, but I am very open to correction.
Concerning spanning trees and Huffman Coding - the tree are constructed from weighted graphs (not that the trees are weighted themselves). However, I understand where you are coming from, where again colloquially (but perhaps not formally), people often refer to and construct weighted trees.
At the beginning of Section 2.3.4 in TAOCP, Knuth makes the following important point concerning graph theory:
"Unfortunately, there will probably never be a standard terminology in this field, and so the author has followed the usual practice of comtemporary books on graph theory, namely to use words that are similar but not identical to the terms used in any other books on graph theory...the nomenclature used here is also biased towards computer applications".
So, in summary, my definition of a tree is open to debate :)
I am grateful for your question because in seeking out the answer, it has deepened my understanding of what a tree is.
[1] Algorithmic Graph Theory and Sage" by David Joyner, Minh Van Nguyen, David Phillip; Version 0.8-r1991;
For clarity, in (computer science) graph theory, a tree is a rooted, strict, connected, undirected, acyclic graph.
Explanation:
rooted: One vertex (also called a node) has been designated the root. The depth of a vertex is the number of branches in the path from root to the vertex. So depth of the root itself is zero and is the only vertex in the tree with this property.
strict: The edges have no weight(s).
connected: A graph is said to be connected if there is a path (edge) between every pair of vertices. From every node to any other node, there is a path to traverse.
undirected: The edges have no directionality specified.
acyclic: The are no closed loops (no cycles of any length).
graph: An abstract data structure consisting of a finite set of vertices and a finite set of edges (vertices pairs).
As another commenter has pointed out, the definition of a tree in mathematics is somewhat different...a tree need not have a root.
Great question - you have touched on the key difference between a labeling scheme and an encoding scheme for tree data structures.
As mentioned previously, the tree is an abstract data type, that is to say, a conceptual model that defines the nodes in a tree, and their relationships.
To be able to evaluate a expression that processes a tree, one needs a labeling scheme. The purpose of a labeling scheme is to assign unique labels to each node in the tree and these labels must facilitate node ordering, and often (but not always) a labeling scheme will permit the reconstruction of the tree structure.
However, no labeling scheme captures the node type, names or the content stored at the nodes. For that we need an encoding scheme. An encoding scheme is constructed upon a labeling scheme and augments it with the information necessary to fully represent the tree in a table-like data structure. In answer to your question, it also permits the full transformation from the table representation to the original tree structure.
Thus, it sounds like what you are looking for is an encoding scheme.
There are many different labeling schemes out there for tree structure data, and virtually all of them can be augmented with additional information to construct a complete encoding scheme. Concerning documented solutions - I have not been active in this space for a number of years, so off the bat - I don't have a recommended documented solution to point you too.
But to help, I will put a link to my PhD thesis [1] which gives a more in-depth understanding of labeling schemes and encoding schemes for tree structured data with an example of a simple implementation of an encoding scheme enabling the full transformation from the table representation to the original tree structure (pages 5-9) and a survey of the advantages and disadvantages of existing labeling schemes concerning their usefulness to be part of an encoding scheme you could use in your solution (see chapter 2)
Caveat 1: My thesis was written in the context of updating dynamic (XML) trees but it addresses the transformation between tree and table data structures.
Caveat 2: The thesis was written 11 years ago, but every now and then I have kept in touch with the latest developments in the area, and to my knowledge, there have been no major developments since.
"A tree-of-objects representation is more difficult to publish in a human-readable form. The objects that comprise the tree tend to all be very different, and thus it is tricky to come up with a consistent and simple table representation with which to display the objects. Any any such table representation that you do come up with would almost certainly have more than six columns, probably many more. The problem of rendering a tree-of-objects as a table is sufficiently difficult that nobody does it"
To further elaborate on this important point.
There is an 'impedance mismatch' (conceptual difficulty mapping between the two logic models) between the tree abstract data type and the table abstract data type. Specifically, there are four key differences between the simple table data structure and the more complex tree data structure that makes mapping between them a non-trivial operation.
Hierarchical: A table has a flat representation; a tree has a hierarchical
representation.
Order: The order of the rows in a table typically do not matter (they may have a unique rowid). The order of branches (nodes) and leaves in a tree is important, and the ordering itself in an encoding of valuable information.
Semi-structured: A table has a fixed structure (rows multiplied by columns). A
tree has a flexible structure - an arbitrary combination of branches (internal nodes) and leaves (terminal nodes). Semi-structured data has a structure that may not necessarily be known in advance, the tree has irregular and variable formation; the tree may have branches with missing or supplementary nodes.
Meta-data: The information describing the meaning of the data in a table
is typically stored separately from the table - consequently a schema is often mandatory. A schema is optional for a tree abstract data type.
As an aside, I have been visiting hacker news almost daily since 2010. This is my first comment on hacker news. I want to say thank you to the community for the many valuable insights over this years.