The On-Line Blog of Integer Sequences

• 2011-10-05 18 notes

  A000602 - Number of n-node unrooted quartic trees; number of n-carbon alkanes C(n)H(2n+2) ignoring stereoisomers

  A000602 - Number of n-node unrooted quartic trees; number of n-carbon alkanes C(n)H(2n+2) ignoring stereoisomers

  1, 1, 1, 1, 2, 3, 5, 9, …

  The chemical we call alcohol is actually more specifically ethyl alcohol (or ethanol). There are other alcohols: methyl alcohol (wood alcohol, similarly intoxicating but poisonous) and isopropyl alcohol (rubbing alcohol) are two of the most common. The simplest alcohols are strings of carbon atoms with a hydroxyl group attached to one of the carbons. In the case of methyl, n = 1, a single carbon atom, has hydroxyl attached, and the three other spots (of the four valences that allow carbon to attach to other atoms) are taken up by hydrogen. Ethyl, n = 2, has two carbons.

              

  Once you get beyond n = 3 (propyl alcohol), the branching behaviors of the four valences in carbon atoms become apparent. Alkane (similar to alcohols, but without the hydroxyl group) examples abound. Butane and isobutane are the two isomers for n = 4. Hexane (n = 6) comes in five different common shapes with sometimes very different properties. Decane (n = 10) has 75 isomers, all of which are flammable liquids.

• 2011-10-03 186 notes

  A084617 - Maximum number of circles with diameter 1 that can be packed in a square of side length n

  A084617 - Maximum number of circles with diameter 1 that can be packed in a square of side length n

  1, 4, 9, 16, 25, 36, 49, 68, …

  Area packing is an interesting field of study. The problems are easy to define to a layperson: How many circles can fit into a square of a given area? What’s the smallest square some number of smaller squares can fit into? Everyone has packed a box or the trunk of a car and can understand the challenges and techniques for packing a set of objects into a given space.

  But the simplicity of understanding the field belies the complexity of the mathematics. The possibilities grow much faster than the number of objects you’re packing. For packing circles in a square, values above about a 5x5 square are conjectures. For packing squares inside the smallest square possible, the best packing for as few as 11 objects has still not been proven.

• 2011-09-30 20 notes

  A139250 - Toothpick sequence

  A139250 - Toothpick sequence

  0, 1, 3, 7, 11, 15, 23, 35, 43, …

  Created by Omar Pol, the toothpick sequence is defined as follows:

  1. At t = 0, there are no toothpicks
  2. At t = 1, there is one toothpick, placed vertically on a plane
  3. To grow from t = n to t = n + 1, place new toothpicks with each of their midpoints touching one endpoint that does not touch another toothpick. All toothpicks must be perpendicular to the toothpick it is touching.

  Here is an animation created by David Applegate of t <= 32:

  

  He also created a JavaScript-powered tool that allows you to play with various conditions and watch the toothpick sequence grow.

• 2011-09-28 8 notes

  A116369 - Day of the week corresponding to Jan 01 of a given year

  A116369 - Day of the week corresponding to Jan 01 of a given year

  7, 2, 3, 4, 5, 7, 1, 2, 3, 5, 6, 7, …

  The only difference between the Gregorian calendar (introduced in 1582 by Pope Gregory XIII) and its predecessor the Julian calendar (introduced in 45 BC by Julius Caesar) is their leap year rules. The older calendar had a leap year every four years, period. The newer one skipped leap years every hundred (except every 400th year did have one). Oh, one other minor difference: ten days in 1582 never happened; in Catholic countries that switched immediately, October 4th, 1582 was followed by October 15th, 1582. In other countries, different dates were skipped (the British Empire didn’t change to the Gregorian calendar until 1752, so for 170 years it was a different date in Britain than it was in France).

  But with the sole exception of years in which switchovers happened, for the past two thousand years, there have only been fourteen possible annual calendars. Every year starts on one of the seven weekdays, and every year is either a leap year or it is not. And there is a pattern to the order of the calendars. Although a true permanent calendar would need a 400-year cycle, in practice you can get away with just 28 years (the lowest common multiple of the 7-day week and the 4-year leap year) until 2100 screws it up.

• 2011-08-26 5 notes

  A003418 - a(0) = 1; for n >= 1, a(n) = least common multiple (or lcm) of {1, 2, …, n}

  A003418 - a(0) = 1; for n >= 1, a(n) = least common multiple (or lcm) of {1, 2, …, n}

  1, 1, 2, 6, 12, 60, 60, …

  The following is a guest post contributed by Brian Ingalls:

  I can’t remember how it came up, but I was talking with some co-workers at a bar the other day about tontines. You may not know them by name, but you might know the episode of The Simpsons called Raging Abe Simpson and His Grumbling Grandson in “The Curse of the Flying Hellfish”. In this episode, Grandpa Simpson was part of a unit in WWII that “found” a bunch of art while raiding a Nazi mansion. They take the art, seal it up, bury it, and form an agreement, that the last member of the unit left alive will own the artwork.

  While having this discussion, I looked up tontines on Wikipedia. I learned that traditionally, a tontine is “an investment scheme for raising capital”. This makes it much more desirable to participate, because you actually get a return on your investment before you are a hundred years old and the last remaining member. Each member of the tontine owns an even share in the investment, and they all get dividends. When someone dies, their share is evenly divided among the remaining members. In this version however, the initial capitol is never returned, and when the final member dies, the agreement is dissolved.

  This got me thinking about what the most effective means for dividing up the initial shares so that the share division process is as easy as possible. I realized that the LCM would be the answer. A number of shares so that when each member dies, their shares are evenly divisible amongst the remaining members.

• 2011-08-12 15 notes

  A077586 - 2^(2^p-1)-1

  A077586 - 2^(2^p-1)-1

  7, 127, 2147483647, …

  A double Mersenne number is a Mersenne number n = 2^k-1 where k is a Mersenne prime. Since the first few Mersenne primes are k = 3, 7, and 31, the first double Mersenne numbers are those shown above. The next one is 2¹²⁷-1, and after that is 2²⁰⁴⁷-1. They quickly get very large.

  But not all Mersenne numbers with a prime exponent are necessarily prime — that’s a necessary condition, but not a sufficient one. The first four double Mersenne numbers are, but the next three (M_M13, M_M17, M_M19, M_M31) are not. The next double Mersenne number, M_M61, is certainly a candidate, but it’s got 7 × 10¹⁷ digits, and no existing factoring method has yet been able to find any factors.

  A distributed search for factors of higher double Mersenne number has been started, but due to the size of the numbers, it may be a very long time indeed until any of them are proven to be prime.

• 2011-08-01 29 notes

  A006877 - In the `3x+1’ problem, these values for the starting value set new records for number of steps to reach 1

  A006877 - In the `3x+1’ problem, these values for the starting value set new records for number of steps to reach 1

  1, 2, 3, 6, 7, 9, 18, 25, …

  In 1937, Lothar Collatz described an operation on positive integers. If the integer is even, divide it by 2. If it is odd, triple it and add one. And then he posed a problem, which has since been called the Collatz conjecture (and a dozen other less common names) — if you apply this operation repeatedly, will it always eventually reach 1, no matter what number you start with?

  The most promising avenues of proof are by disproving the alternatives. If the Collatz conjecture were false, that would mean that one of the following alternatives were true:

  1. For some odd n, there is an infinitely divergent series, i.e. 3n+1 is odd, and 3(3n+1)+1 is odd, and so forth forever, it never equals 2^k for any k, or
  2. There exists a cycle which does not include 1

  Tim Conway and Jeffrey Lagarias each examined the latter alternative through the 70s and 80s, Lagarias proving that there are no cycles of length < 275,000. More recently, several researchers (most recently Oliveira e Silva) have searched for some n that does not have a finite path to 1. So far, no counter-examples are known through at least 5 × 10¹⁸.

  Unfortunately, the Collatz Conjecture may never be proved. Paul Erdős himself once said “mathematics is not yet ready for such problems” in reference to this problem. He may have been right — In 1972, Conway proved that general Collatz-type problems can be formally undecidable.

• 2011-07-27 5 notes

  A033623 - Grundy function for turn-at-most-4-coins game.

  A033623 - Grundy function for turn-at-most-4-coins game.

  1, 2, 4, 8, 15, 16, 32, 51, …

  Impartial games are those where there is no hidden information, no element of chance, and you don’t need to know whose turn it is to determine the optimal move. Tic-tac-toe and chess are not impartial games. In those cases, since each player has her own pieces (X’s, or white), the optimal move for one player is not always the same as that for the other. The simplest (and in some ways, canonical) impartial game is Nim. The game starts with several piles of tokens. Players alternate turns taking one or more tokens from any one pile. Typically, the player who takes the last token loses (this type of impartial game is called “misère”), but the rule can be flipped (“normal play”).

  The Sprague-Grundy theorem (discovered independently by two mathematicians in the 1930s) shows that normal play impartial games of any sort are always equivalent to a game of Nim of sufficient size. By mapping the game states of a game to a directional graph and then assigning values (called nim values or nimbers) to the game states, you can determine the optimal play for any normal play impartial game.

• 2011-07-22 43 notes

  A140267 - Nonnegative integers in balanced ternary representation (with 2 standing for -1 digit)

  A140267 - Nonnegative integers in balanced ternary representation (with 2 standing for -1 digit)

  0, 1, 12, 10, 11, 122, 120, …

  In number bases that most people are familiar with (decimal, binary, octal, etc), all of the digits represent positive values. There is no digit that could appear in the ones place that would represent a negative value. You would have to place a minus symbol before the number. In signed-digit representations, however, there are digits that represent negative numbers. Balanced forms are a special subset of signed-digit representations where for a base k, there are digits for all values between -⌊k/2⌋ and ⌊k/2⌋. Balanced ternary, for instance, has values for -1, 0, and 1. (These are usually written as +, 0, and -).

  At first, this can be confusing. Like standard ternary, it is easy to represent powers of 3:

  • 1 = 3⁰ = +
  • 3 = 3¹ = +0
  • 9 = 3² = +00

  Numbers one less than a power of three have a - digit in the ones position:

  • 2 = 3¹ - 1 = +-
  • 8 = 3² - 1 = +0-

  Other numbers can be constructed with a little bit more thought.

  But of what use is balanced ternary? The most valuable use is in fast integer arithmetic. The single-digit addition tables for balanced ternary requires 33% fewer carries. And multiplication tables need no carried digits at all. Some fast math libraries are therefore implemented with balanced ternary, and CPUs that use balanced ternary at the circuitry level can be simpler, faster, and require less power. (Hypothetically, two-pan balances and monetary systems could be improved with a balanced ternary system, but the complexities of doing power-of-three math in ones head probably means this will never be implemented.)

• 2011-07-13 46 notes

  A105386 - Morse code alphabet where “.” = 0 and “-” = 1.

  A105386 - Morse code alphabet where “.” = 0 and “-” = 1.

  1, 8, 10, 4, 0, 2, 6, 0, …

  The electrical telegraph was not the first method for transmitting information over long distances. For centuries, a number of non-electrical visual communication mechanisms were in wide use. Claude Chappe’s semaphore network was widely used in France for most of the first half of the 19th century, especially by Napoleon to coordinate his armies. The Prussian semaphore system transmitted instructions hundreds of miles for several decades. And smoke signals and reflected light signals have been used by indigenous peoples since ancient times.

  When the first electrical telegraph was invented by Samuel Thomas von Sömmering in 1809, it used up to 35 different wires — one for almost every letter and number. Gauss and Weber’s telegraph was the first to be used for regular communication, and although it encoded letters onto two wires, they chose to use a system of binary representation: a current in one direction was a 0, in the opposite direction was a 1. Samuel Morse’s electric telegraph was the first commercially viable system in the United States, and the encoding system that he and/or Alfred Vail invented made it fast and simple to send text messages.

  The telegraph spread wildly. In 1838, he sent the first telegram a distance of 2 miles. In 1844, he sent a message from Washington, DC to Baltimore (about 40 miles). By 1861, the telegraph stretched from coast to coast and the Pony Express was abandoned as a result. In 1966, the first trans-Atlantic telegraph line was laid, and in 1902 cables also stretched across the Pacific, encircling the world in telegraphy.