Number of \$n\$-carbon alkanes

16

3

Given a positive number \$n\$, find the number of alkanes with \$n\$ carbon atoms, ignoring stereoisomers; or equivalently, the number of unlabeled trees with \$n\$ nodes, such that every node has degree \$\le 4\$.

This is OEIS sequence A000602.

See also: Paraffins - Rosetta Code

Example

For \$n = 7\$, the answer is \$9\$, because heptane has nine isomers:

  • Heptane: \$\mathrm{H_3C-CH_2-CH_2-CH_2-CH_2-CH_2-CH_3}\$

Heptane

  • 2-Methylhexane: \$\mathrm{H_3C-CH(CH_3)-CH_2-CH_2-CH_2-CH_3}\$

2-Methylhexane

  • 3-Methylhexane: \$\mathrm{H_3C-CH_2-CH(CH_3)-CH_2-CH_2-CH_3}\$

3-Methylhexane

  • 2,2-Dimethylpentane: \$\mathrm{H_3C-C(CH_3)_2-CH_2-CH_2-CH_3}\$

2,2-Dimethylpentane

  • 2,3-Dimethylpentane: \$\mathrm{H_3C-CH(CH_3)-CH(CH_3)-CH_2-CH_3}\$

2,3-Dimethylpentane

  • 2,4-Dimethylpentane: \$\mathrm{H_3C-CH(CH_3)-CH_2-CH(CH_3)-CH_3}\$

2,4-Dimethylpentane

  • 3,3-Dimethylpentane: \$\mathrm{H_3C-CH_2-C(CH_3)_2-CH_2-CH_3}\$

3,3-Dimethylpentane

  • 3-Ethylpentane: \$\mathrm{H_3C-CH_2-C(CH_2CH_3)-CH_2-CH_3}\$

3-Ethylpentane

  • 2,2,3-Trimethylbutane: \$\mathrm{H_3C-C(CH_3)_2-CH(CH_3)-CH_3}\$

2,2,3-Trimethylbutane

Note that 3-methylhexane and 2,3-dimethylpentane are chiral, but we ignore stereoisomers here.

Test cases

You don't need to handle the case \$n = 0\$.

intput	output
=============
0	1
1	1
2	1
3	1
4	2
5	3
6	5
7	9
8	18
9	35
10	75
11	159
12	355
13	802
14	1858
15	4347
16	10359
17	24894
18	60523
19	148284
20	366319

alephalpha

Posted 2019-01-11T05:25:34.243

Reputation: 23 988

3

I'd be impressed if someone manages to write a solution with Alchemist!

– ბიმო – 2019-01-11T10:23:04.443

@PeterTaylor Well It can output each time a digit – l4m2 – 2019-01-11T17:17:10.600

@BMO Also Alchemist looks turing complete if big number support

– l4m2 – 2019-01-11T17:20:54.750

@l4m2: I used it before for a [tag:sequence] challenge and some [tag:number] challenges, you can also use unary output which is most likely easier. And yes, it is most likely TC (uses bignums), I haven't formally proved it though.

– ბიმო – 2019-01-11T17:27:38.980

@BMO It looks to just able to simulate CM – l4m2 – 2019-01-11T17:29:01.180

set 1: { INC (r) S1->S2+r, DEC (r) S1+r->S2, JZ (r, z) S1+0r->z S1+r->S2+r} – l4m2 – 2019-01-11T17:32:48.130

Answers

11

CJam (100 98 91 89 83 bytes)

1a{_[XX]*\_{_0a*}:E~\{E\_{ff*W%{0@+.+}*}:C~.+2f/}:D~.+C.+3f/1\+}q~:I*DE1$D.-X\+.+I=

Takes input from stdin, outputs to stdout. Note that this exploits the licence to not handle input 0 to save two bytes by inlining the definitions of C and D. Online demo

NB this is very slow and memory-inefficient. By trimming arrays a much faster version is obtained (3 bytes more). Online demo.

Dissection

OEIS gives (modulo an indexing error) the generating function decomposition $$\begin{eqnarray} A000598(x) &=& 1 + x Z(S_3; A000598(x)) \\ A000678(x) &=& x Z(S_4; A000598(x)) \\ A000599(x) &=& Z(S_2; A000598(x) - 1) \\ A000602(x) &=& A000678(x) - A000599(x) + A000598(x^2) \\ \end{eqnarray}$$ where \$Z(S_n; f(x))\$ denotes the cycle index of the symmetric group \$S_n\$ applied to the function \$f(x)\$.

I manipulated this into a slightly golfier decomposition, and then looked up the intermediate sequences and discovered that they're also in OEIS:

$$\begin{eqnarray} A000642(x) &=& Z(S_2, A000598(x)) \\ A000631(x) &=& Z(S_2, A000642(x)) \\ A000602(x) &=& A000642(x) + x A000642(x^2) - x A000631(x) \end{eqnarray}$$

Earlier versions reused block C (convolve two polynomials) from this answer. I've found a much shorter one, but I can't update that answer because it's from a chaining question.

1a            e# Starting from [1]...
{             e# Loop I times (see below) to build A000598 by f -> 1 + Z(S_3; f)
  _[XX]*      e#   Copy and double-inflate to f(x^3)
  \_          e#   Flip and copy: stack is f(x^3) f(x) f(x)
  {_0a*}:E~   e#   Assign copy-and-inflate to E and execute
              e#   Stack: f(x^3) f(x) f(x) f(x^2)
  \           e#   Flip
  {           e#   Define and execute block D, which applies f -> Z(S_2;f)
              e#     Stack: ... f
    E\_       e#     Stack: ... f(x^2) f(x) f(x)
    {         e#     Define and execute block C, which convolves two sequences
      ff*     e#       Multiply copies of the second sequence by each term of the first
      W%      e#       Reverse
      {       e#       Fold
        0@+.+ e#         Prepend a 0 to the first and pointwise sum
      }*
    }:C~      e#     Stack: ... f(x^2) f(x)^2
    .+2f/     e#     Pointwise average
  }:D~        e#   Stack: f(x^3) f(x) f(x^2) Z(S_2;f(x))
  .+C         e#   Stack: f(x^3) f(x)*(f(x^2) + Z(S_2;f(x)))
  .+3f/       e#   Add and divide by 3 to finish computing Z(S_3; f)
  1\+         e#   Prepend a 1
}
q~:I          e# Read input to I
*             e# Loop that many times
              e# Stack: I+1 terms of A000598 followed by junk
D             e# Stack: I+1 terms of A000642 followed by junk
E1$D          e# Stack: A000642 A000642(x^2) A000631
.-X\+.+       e# Stack: A000602
I=            e# Extract term I

Peter Taylor

Posted 2019-01-11T05:25:34.243

Reputation: 41 901

6

Alchemist (1547 bytes)

_->In_NN+2b+al+g
al+g+0NN->ak
al+g+NN->ah
ah+b->ah+m+d+z+a
ah+0b->C+Z+Q
Z+j+z->Z+j+d
Z+j+0z->M+s
M+g+b->M+g+r
M+g+h->M+g+d
M+g+0b+0h+q->J+U
J+o+h->J+o+m
J+o+a->J+o+d
J+o+0h+0a->2C+an+Q
an+j+h->an+j+d
an+j+0h->aC+s
aC+g->e+am+P
am+l+b->am+l+d
am+l+0b->al+s
ak+b->ak+m+d
ak+0b->C+aj+Q
aj+j+h->aj+j+b
aj+j+0h->I+n
I+f+e->I+f+a
I+f+b->I+f+m+d+z
I+f+0e+0b->C+ai+Q
ai+j+h->ai+j+b
ai+j+0h->aB+n
aB+f->H
H+z->H+d
H+a+e->H
H+0z+0e->G+i
G+i+0b->ag
G+i+b->az+b+n
az+f+0b->Out_a
az+f+b->G+b+n
G+f->G+t
ag+e->ag
ag+0e->af+t
af+i+e->af+i+a
af+i+0e->Out_a
Q->F+s
F+g+b->F+g+y
F+g+A->F+g
F+g+0b+0A->av+o
av+o+0m->w
av+o+m->m+ae+A
ae+m->ae+b
ae+0m->u+n
u+f+b->u+f+m
u+f+e->u+f+E
u+f+A->u+f+k+c
u+f+0b+0e+0A->ad
ad+c->ad+A
ad+0c->ac
ac+y->ac+d+c
ac+0y->ab
ab+c->ab+y
ab+0c->V+l
V+l+0k->x
V+l+k->aa+t
aa+i+0e->W
aa+i+e->Y
Y+E->Y+D+c
Y+0E->X
X+c->X+E
X+0c->aa+i
W+D->W+e
W+0D->V+P
x+E->x
x+d->x
x+b->x+k
x+0E+0d+0b->aw
aw+h->aw+d
aw+0h->aE+s
aE+g->p
p+b->p+2r
p+k->p+d
p+B->p
p+q->p
p+0b+0k+0B+0q->r+q+av+U
w+h->w+d
w+y->w+r
w+C->w+B+q
w+0h+0y+0C->aD+U
aD+o->j
U->au+s
au+g+b->au+g+d
au+g+0b->v
v+d->d+aA+t
aA+i+k->R
aA+i+0k->at
at+B->at+k+c
at+0B->L
L+c->L+B
L+r->L+b
L+0c+0r->as+n
as+f+b->as+f+r
as+f+0b->R
R+0e->K
R+e+q->ar+D+c
ar+e+q->ar+c
ar+0q->aq
aq+c->aq+q
aq+0c->R
K+D->K+e
K+h->K+b
K+0D+0h->ap+P
ap+l+b->ap+l+h
ap+l+0b->v
v+0d+k->v
v+0d+r->v
v+0d+0k+0r->o
s+0d->g
s+d->d+ao+t
ao+i->ao+P
ao+l->s
P->O+c
O+b->2c+O
O+0b->N
N+c->b+N
N+0c+e->O
N+0c+0e->l
n+b->n+c
n+0b->T
T+c->ay
T+0c->e+n
ay+c->b+T
ay+0c->f
t+d->t+c
t+0d->S
S+c->ax
S+0c->e+t
ax+c->d+S
ax+0c->i

Online demo.

Note: this is quite slow. If testing with an interpreter which supports applying a rule multiple times at once (e.g. my one - although make sure you have the latest version which fixes a bug in the parser) then you can get a significant speed-up by adding two rules:

T+2c->b+T
S+2c->d+S

which inline a route through the existing rules

T+c->ay
ay+c->b+T
S+c->ax
ax+c->d+S

Partial dissection

At a high level, this uses the same approach as my CJam answer.

The computation model of Alchemist is essentially the Minsky register machine. However, Alchemist very nicely exposes the equivalence of code and data, and by allowing many tokens on the left hand side of a production rule effectively the state is not constrained to be represented by one atom: we can use a tuple of atoms, and this allows (non-recursive) subroutines. This is very useful for golf. The only things it's really lacking are macros and debuggability.

For arrays I'm using a pairing function which can be implemented quite golfily in RMs. The empty array is represented by \$0\$, and the result of prepending \$x\$ to array \$A\$ is \$(2A+1)2^x\$. There is one subroutine to pair: the subroutine is called P and it prepends the value of e to b. There are two subroutines to unpair: n unpairs b to e and b; and t unpairs d to e and d. This allowed me to save quite a bit of shuffling data between variables, which is important: a single "move" operation

a, b = b, 0

expands to at least 17 bytes:

S+a->S+b
S+0a->T

where S is the current state and T is the next state. A non-destructive "copy" is even more expensive, because it has to be done as a "move" from a to b and an auxiliary tmp, followed by a "move" from tmp back to a.

Obfuscation

I aliased various variables to each other and eliminated about 60 states in the process of golfing the program, and many of them didn't have particularly meaningful names anyway, but to fully golf it I wrote an minimiser so the names are now thoroughly indecipherable. Good luck reverse engineering it! Here is the minimiser (in CJam), which makes a few assumptions about the code but could be adapted to minimise other Alchemist programs:

e# Obfuscate / minimise Alchemist program

e# Tokenise
qN%[SNS]e_*S%

e# Get token frequencies for substitution purposes, special-casing the I/O ones
_["+" "0" "2" "->" "_" N "In_n" "n" "Out_tmp2" "tmp2"]-
$e`$W%1f=

e# Empirically we want a two-char input for n and a one-char one for tmp2
["In_n" "Out_tmp2" "n" "tmp2"]\+
["In_NN" "Out_a" "NN"] "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"1/:A+ A2m*:e_"NN"a-+
1$,<

er
_s,p

Peter Taylor

Posted 2019-01-11T05:25:34.243

Reputation: 41 901

Wait... does that interpreter work? AFAICT... you pick a random rule, then figure out how many times that can be applied. Does that even work correctly? – ASCII-only – 2019-02-07T22:32:09.030

Hmm. How would you improve debuggability – ASCII-only – 2019-02-07T22:33:24.613

@ASCII-only, that would work but it's not actually what it does. It first picks a rule which is applicable and then works out how many times it can be applied. Debuggability is tricky. One of my ideas for a dissertation project back in the day was a GUI RM editor with backwards debugger. – Peter Taylor – 2019-02-07T22:52:00.750

but... rule execution order affects program order does it not – ASCII-only – 2019-02-08T00:52:18.393

@ASCII-only, yes. That's why there are so many variables. Only about 16 of them are data: the rest are state. I've used non-determinism to golf by effectively parallelising independent "move" operations. – Peter Taylor – 2019-02-08T07:48:35.447

i meant that in some programs, if you do as many applications of a certain rule as possible when there are multiple applicable rules, the possible results may be restricted compared to the official interpreter? – ASCII-only – 2019-02-08T11:15:13.180

@ASCII-only, oh, I thought you were worried about this program. If it's the interpreter in general, see the last point in the roadmap. – Peter Taylor – 2019-02-08T11:42:08.283

I wouldn't say it's the ability to analyse though, but if that's what you meant by "ability to analyse" then fair enough – ASCII-only – 2019-02-11T05:44:35.963

5

Node.js 11.6.0,  229 223 221  218 bytes

Derived from the Java implementation suggested on Rosetta Code.

f=(N,L=1,u=[...r=[c=[],1,...Buffer(N)]],k=u[(g=(n,B,S,i,b=B,m,d=0)=>{for(;++b<5;)for(x=c[B]=(d+r[m=n])*(d++?c[B]/d:i),u[S+=n]+=L*2<S&&x,r[S]+=b<4&&x;--m;)g(m,b,S,c[B])})(L,0,1,1),L]-=~(x=r[L++/2])*x>>1)=>L>N?k:f(N,L,u)

Try it online!

Arnauld

Posted 2019-01-11T05:25:34.243

Reputation: 111 334

1

Pari/GP, 118 bytes

A direct translation of Peter Taylor's CJam answer.

n->(s(k)=subst(a,x,x^k));(z()=(a^2+s(2))/2);a=O(1);for(i=0,n,a=1+x*(a*z()+(s(3)-a^3)/3));a=z();Pol(a+x*(s(2)-z()))\x^n

Try it online!

alephalpha

Posted 2019-01-11T05:25:34.243

Reputation: 23 988