15
\$\begingroup\$

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
\$\endgroup\$
  • 3
    \$\begingroup\$ I'd be impressed if someone manages to write a solution with Alchemist! \$\endgroup\$ – BMO Jan 11 at 10:23
  • \$\begingroup\$ @PeterTaylor Well It can output each time a digit \$\endgroup\$ – l4m2 Jan 11 at 17:17
  • \$\begingroup\$ @BMO Also Alchemist looks turing complete if big number support \$\endgroup\$ – l4m2 Jan 11 at 17:20
  • \$\begingroup\$ @l4m2: I used it before for a sequence challenge and some 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. \$\endgroup\$ – BMO Jan 11 at 17:27
  • \$\begingroup\$ @BMO It looks to just able to simulate CM \$\endgroup\$ – l4m2 Jan 11 at 17:29
10
+100
\$\begingroup\$

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
\$\endgroup\$
5
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.