All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Unique Necklaces (Posted on 2004-08-18)

There is no clasp to identify a specific point on the chain, and a flipped over necklace is still the same necklace.
_____________________________

To get you started:

With 1 bead, the necklace can be either 1 black or 1 white bead.

With 2 beads, the necklace can be either 2 black, 2 white, or 1 black-1 white

With 3 beads, the necklace can be either 3 black, 3 white, 2 black-1 white, 2 white-1 black, etc...

```# Beads  Number of Necklaces
1          2
2          3
3          4
4          6
5          8
6         13
```

 No Solution Yet Submitted by SilverKnight Rating: 4.0000 (4 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 Beyond me, but... (spoiler) | Comment 2 of 15 |

The derivation of a solution is beyond me.  Apparently mathematicians have figured this out, so an internet search helps.

Fortunately, SK has provided a list of the first few and so this can be treated like a Sequences problem, and a search of the online handbook of integer sequences (http://www.research.att.com/~njas/sequences/) brings up a formula involving the Euler Phi function.  PlanetMath.org/encyclopedia has an article on the Euler Phi function that aids in its calculation.

The formula for the sequence as given in the online handbook is
Sum_{ d divides n } phi(d)*2^(n/d)/(2*n) + either 2^((n-1)/2) if n odd
or 2^(n/2-1)+2^(n/2-2) if n even.

And the formula for the phi function of d is

d * Product{all primes p that divide d} (1 - 1/p)

so for example phi(2000) = 2000 * (1-1/2) * (1-1/5) = 800.

The following program implements these algorithms:

1000   for N=1 to 47
1010    Tot=0
1020    for D=1 to N
1030       if N@D=0 then
1040         :Tot=Tot+fnPhi(D)*2^(N//D)//(2*N)
1050    next
1060    if N@2=0 then
1070      :Tot=Tot+2^(N//2-1)+2^(N//2-2)
1080     :else
1090      :Tot=Tot+2^((N-1)//2)
1100    print N,Tot
1110   next
1999   end
2000   ' Phi function defined ----
2010   fnPhi(X)
2020   local Temp,Dvsr,Answ,Lmt
2030   Temp=X:Lmt=(X)
2040   Answ=X
2050   Dvsr=1
2060   while Dvsr<Lmt
2070    Dvsr=nxtprm(Dvsr)
2080    if Temp@Dvsr=0 then
2090      :Answ=Answ*(Dvsr-1)//Dvsr
2100      :while Temp@Dvsr=0
2110         :Temp=Temp//Dvsr
2120      :wend
2140   wend
2150   return(Answ)

` 1       2 2       3 3       4 4       6 5       8 6       13 7       18 8       30 9       46 10      78 11      126 12      224 13      380 14      687 15      1224 16      2250 17      4112 18      7685 19      14310 20      27012 21      50964 22      96909 23      184410 24      352698 25      675188 26      1296858 27      2493726 28      4806078 29      9272780 30      17920860 31      34669602 32      67159050 33      130216124 34      252745368 35      490984488 36      954637558 37      1857545300 38      3617214681 39      7048675960 40      13744694928 41      26818405352 42      52359294790 43      102282248574 44      199914398490 45      390941662712 46      764884036743 47      1497215711538`

and this continues as:

` 48      2932043766538 49      5744404057034 50      11259024569838 51      22076502318624 52      43303893547956 53      84973644983780 54      166800088109829 55      327534652572024 56      643371579062292 57      1264168584899532 58      2484745029278898 59      4885261149611790 60      9607680019329456 61      18900353608280300 62      37191017905571379 63      73201367519380268 64      144115191330636810 65      283796066967422192 66      558992251165454994 67      1101298162244236182 68      2170205198153526576 69      4277505889344524468 70      8432797316853883164 71      16628051030379615882 72      32794211738611821312 73      64689951888851602952 74      127631526668052321918 75      251859545890487146472 76      497091208931087393202 77      981270957754284704684 78      1937381121593132140708 79      3825714619583392442706 80      7555786373422938025200 81      14925010119798638898462 82      29485995602019485259228 83      58261485284831754566694 84      115135792347575114543648 85      227562507225975302929472 86      449832863119068367872573 87      889324740874730204724120 88      1758437555816391076574364 89      3477359660931581722277912 90      6877444662723140842510068 91      13603736695478923656694872 92      26911739984517947581815054 93      53244732872559842956478532 94      105356599088223771924108747`

and in each instance each successive value is almost twice the preceding value, the more so as the numbers get larger.

 Posted by Charlie on 2004-08-18 15:04:00

 Search: Search body:
Forums (0)