## Welcome to BrainDen.com - Brain Teasers Forum

 Welcome to BrainDen.com - Brain Teasers Forum. Like most online communities you must register to post in our community, but don't worry this is a simple free process. To be a part of BrainDen Forums you may create a new account or sign in if you already have an account. As a member you could start new topics, reply to others, subscribe to topics/forums to get automatic updates, get your own profile and make new friends. Of course, you can also enjoy our collection of amazing optical illusions and cool math games. If you like our site, you may support us by simply clicking Google "+1" or Facebook "Like" buttons at the top. If you have a website, we would appreciate a little link to BrainDen. Thanks and enjoy the Den :-)
Guest Message by DevFuse

# Unique Codes

Best Answer m00li, 27 April 2014 - 01:05 PM

Spoiler for Still struggling with it but

EDIT: the last term for F(n) should read n-[n/2]C[n/2]f(n-[n/2]) where [k] is the max integer <=k

Go to the full post

13 replies to this topic

### #11 plasmid

plasmid

Senior Lolcat

• VIP
• 1483 posts
• Gender:Male

Posted 27 April 2014 - 04:21 PM

Spoiler for partial solution
It looks like it's heading towards DrXP's solution, but I can't tell for sure.
• 0

### #12 m00li

m00li

Junior Member

• Members
• 71 posts

Posted 29 April 2014 - 11:12 PM

I still think the correct answer for n digit string is given by

= nC0f(n) + n-1C1f(n-1) + n-2C2f(n-2) + n-3C3f(n-3) + ......    +  n-[n/2]C[n/2]f(n-[n/2])
putting n = 10, we get F(10) = 3349507;
where f(n) = (subfactorial(n+1))/n

I wrote a vba code to do the simulation and it confirms the answer too. The values for first few n's are:

n F(n) 3 5 4 21 5 106 6 720 7 4547 8 36696 9 332769 10 3349507

Here's the vba code:

Dim arrlen As Integer
Dim counter As Long
Sub randomd()
j = 1
position = 1
counter = 0
Dim i_arr As Variant
i_arr = Array(1, 3, 7, 4, 10, 6, 8, 2, 9, 5)
arrlen = UBound(i_arr) + 1
ReDim Preserve i_arr(1 To arrlen)
Call perm(ByVal i_arr, j, ByVal position)
Sheet2.Cells(1, arrlen + 1) = counter
End Sub

Sub perm(ByVal i_arr, ByRef j, ByVal position)
For i = position To arrlen
temp = i_arr(position)
i_arr(position) = i_arr(i)
i_arr(i) = temp
If position = arrlen Then
'For k = 1 To position: Sheet2.Cells(j, k) = i_arr(k): Next k
satisfies = True
k = 3
While satisfies And k <= arrlen
If i_arr(k) - i_arr(k - 1) = 1 And i_arr(k - 1) - i_arr(k - 2) = 1 And satisfies Then satisfies = False
k = k + 1
Wend
If satisfies Then counter = counter + 1
j = j + 1
End If
Call perm(ByVal i_arr, j, ByVal position + 1)
Next i
End Sub

• 0

### #13 m00li

m00li

Junior Member

• Members
• 71 posts

Posted 30 April 2014 - 06:06 AM

I still think the correct answer for n digit string is given by

= nC0f(n) + n-1C1f(n-1) + n-2C2f(n-2) + n-3C3f(n-3) + ......    +  n-[n/2]C[n/2]f(n-[n/2])
putting n = 10, we get F(10) = 3349507;
where f(n) = (subfactorial(n+1))/n

I wrote a vba code to do the simulation and it confirms the answer too. The values for first few n's are:

n                             F(n)
3                              5
4                             21
5                           106
6                           643
7                        4547
8                      36696
9                    332769
10                3349507

Here's the vba code:

Dim arrlen As Integer
Dim counter As Long
Sub randomd()
j = 1
position = 1
counter = 0
Dim i_arr As Variant
i_arr = Array(1, 3, 7, 4, 10, 6, 8, 2, 9, 5)
arrlen = UBound(i_arr) + 1
ReDim Preserve i_arr(1 To arrlen)
Call perm(ByVal i_arr, j, ByVal position)
Sheet2.Cells(1, arrlen + 1) = counter
End Sub

Sub perm(ByVal i_arr, ByRef j, ByVal position)
For i = position To arrlen
temp = i_arr(position)
i_arr(position) = i_arr(i)
i_arr(i) = temp
If position = arrlen Then
'For k = 1 To position: Sheet2.Cells(j, k) = i_arr(k): Next k
satisfies = True
k = 3
While satisfies And k <= arrlen
If i_arr(k) - i_arr(k - 1) = 1 And i_arr(k - 1) - i_arr(k - 2) = 1 And satisfies Then satisfies = False
k = k + 1
Wend
If satisfies Then counter = counter + 1
j = j + 1
End If
Call perm(ByVal i_arr, j, ByVal position + 1)
Next i
End Sub

EDIT: corrected the n:F(n) table above

• 0

### #14 plasmid

plasmid

Senior Lolcat

• VIP
• 1483 posts
• Gender:Male

Posted 30 April 2014 - 03:30 PM

m00li's answer of 3349507 seems correct. I couldn't follow the VB code's logic for making permutations (a subroutine seems to be calling itself?) and I don't have MS Office, so I wrote a perl script to calculate it, and it gave the same answer.

```#!/usr/bin/perl
use strict;
use warnings;

# The "implicit" starting permutation for this program to
# avoid copying any triplets from is
# 0 1 2 3 4 5 6 7 8 9
# since that makes programming easier.
# This will generate permuatations, see if any
# triplets appear in the permutation, and if not then
# print the permutation and increase the counter

my \$counter = 0;

# This uses List::Permutor to generate permutations
# If you don't already have it installed, from the command
# prompt, run "cpan List::Permutor"
# (or run "cpan App::cpanminus" then "cpanm List::Permutor")

use List::Permutor;
my \$permutor = List::Permutor -> new(0..9);
while (my @perm = \$permutor -> next()) {
# For each permutation, check for consecutive triplets
# If there are no triplets, increase the counter and print
# the permutation
my \$notriplets = 1;
TRIPLETLOOP: for(my \$triplet=0; \$triplet<8; \$triplet++) {
if((\$perm[\$triplet] == \$perm[\$triplet+1]-1) &&
(\$perm[\$triplet] == \$perm[\$triplet+2]-2)) {
\$notriplets = 0;
last TRIPLETLOOP;
}
}
if(\$notriplets) {
print "Permutation " . ++\$counter . ": @perm\n";
}
}
print "Found \$counter permutations with no triplets\n";```
I also couldn't understand post 10 at first, but now it seems to make sense.
• 0

#### 0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users