Topic: Red Phish DeBruijn 52
 Message: Posted by: glowball (Nov 22, 2018 03:00AM)
Using an all blue back deck a spectator cuts the deck several times and then takes the top card. Then five more spectators take a card from the top. The magician then asks who is holding a red card (ie: hearts or diamonds). The magician then names all six cards.

Most places on the internet that describe this trick either use a 32 card deck, or 3 repeating 16 cards or a 52 card deck that does not wrap.
What this post describes is a 52 card deck that utilizes my wrapping DeBruijn 52 bits but add the two jokers to make the 28 binary "1" black cards and remove two red cards (a Heart and a Diamond) because we must have exactly 52 cards.

The Jokers must be perceived as black cards (no red coloring on them, no ambiguity) for the statement "let me know if you are thinking of a red card". To do this trick we must have an entirely new stack. To create your stack initially: permanently remove the two red 8s ie: 8D and 8H then from a well-mixed deck insert the 24 red cards to the binary "0" positions and insert the clubs, spades, 2 jokers to the binary "1" positions. The use of the jokers is needed because my DeBruijn 52 does not split 26-26 (zeros and ones).

Yelnif 52 DeBruijn:
0 0 0 0 0 0 1 1 1 1 1 1
0 0 0 1 1 0 1 0 0 0 1
0 0 1 1 0 0 1 0 1 1 1
0 0 1 1 1 0 1 1 0 1 1 1 1
0 1 0 1 1
Record your setup on paper and keep it somewhere safe so you can re-create your deck again should it get mixed up.

Then create another sheet, a crib sheet with 52 Rows.
Each row will have a two digit number which is the interpretation of the six binary bits. On that row will be an abbreviated notation of the six cards. The rows on the crib sheet must be sorted from low to high to make it easy for you to find the number. You could cut and paste the crib sheet inside a book a such as "Future Mysterious Events" (or something like that) to give you an excuse for looking up the crib sheet info.

PS: I doubt that a 26-26 DeBruijn is possible, I tried many hours to create a 26-26 and was unsuccessful. If someone ever develops one then no need to add the 2 jokers and no need to remove the 2 red cards.
 Message: Posted by: TomasB (Nov 23, 2018 01:03AM)
For 26/26 there seem to be plenty, such as these (and of course you can switch all zeros for ones and vice versa):

1111110010101101100110100100111011100000010001100010

1111110111100101001101000010010001110101011000001100

1111110111010001111000100000011001001101011011000010

1111110101111001011010000110001110111000000100010100

1111110111010100000110010001011011000010010101111000

1111110000101100011010011001010100010000011110101110

1111110111010110000101111000100000011010010100011100

1111101000011000001000101101010010101110011110001110

1111100101000111101001100111000010000011011101100010

1111101100001001101111001011101011010001010100100000

1111100001001000001100110100111001010001111010101110

1111100001001101011110111001011001110100010100100000

1111100000111001100011011010000101100100101010011110

1111101010110010011000000110111011010010100011100010

/Tomas
 Message: Posted by: glowball (Nov 23, 2018 10:11AM)
Okay everyone forget the part about using the joker's and removing two red cards because Tomas has supplied the answer!

I'm just going to use the first string:

1111110010101101100110100100111011100000010001100010

Tomas, just curious where did you find these?

And thanks so much!!
 Message: Posted by: glowball (Nov 23, 2018 09:46PM)
Below from TomasB from themagicafe (glowball added the letter to identify/talk about these DeBruijns):
A. 1111110010101101100110100100111011100000010001100010

B. 1111110111100101001101000010010001110101011000001100

C. 1111110111010001111000100000011001001101011011000010

D. 1111110101111001011010000110001110111000000100010100

E. 1111110111010100000110010001011011000010010101111000

F. 1111110000101100011010011001010100010000011110101110

G. 1111110111010110000101111000100000011010010100011100

H. 1111101000011000001000101101010010101110011110001110

I. 1111100101000111101001100111000010000011011101100010

J. 1111101100001001101111001011101011010001010100100000

K. 1111100001001000001100110100111001010001111010101110

L. 1111100001001101011110111001011001110100010100100000

M. 1111100000111001100011011010000101100100101010011110

N. 1111101010110010011000000110111011010010100011100010

I changed my mind again and like your tenth DeBruijn "J" better and will use it because it has clumps of just 5 "1"s and 5 "0"s instead of 6 "1"s and 6 "0"s (I think a face up deck spread at the beginning using "J" just looks better than the first DeBruijn "A" because less red/black cards are in a group in "J").

This also means the spectator will never cut to 6 red cards nor 6 black cards (which might tip the method a little bit). Actually H, I, J, K, L, M DeBruijn's above have this 5 max feature (note that "N" has 6 "0"s).

Another benefit of "J" is that it has nice mixture of "1"s and "0"s in the middle should the spectator do only one cut of the deck.

J. 1111101100001001101111001011101011010001010100100000

In preparation I will move the first two cards (red cards) to the bottom and keep it that way in the card case (breaks up the view of 5 red cards a little more when spreading the deck at the beginning):
J. 1110110000100110111100101110101101000101010010000011

Tomas, I soooooo appreciate your information!
 Message: Posted by: TomasB (Nov 27, 2018 04:01AM)
You are welcome, but I've done nothing more fancy than a random search, so nothing exhaustive at all. But the program spits out lots of solutions quickly so I think there are way more.

I like your restriction of what makes a good solution, so I forced this which makes it much quicker since it's only the middle 40 cards I need to randomize.

1111101011110011001010010011100001011011000110100000
1111101010110011000101110111100100101001110000100000
1111101001010110011101101110010011000110101000100000
1111101000110011101111001001101100001010111000100000
1111101110010011001110101111000100001010001101100000
1111101110010011010110011101001010001011110000100000
1111100110110001000110010011101000010101111011100000
1111100111010010000100110010101000101111011011100000
1111100010001100100110101011011110110000101110100000
1111100001011100110010100011010101101111011000100000
1111100001000101100011010100101011110111001110100000

Are there any more specific restrictions you'd like on the solution? Maybe there is a totally symmetrical solution so the deck is sort of in a stay stack? That would be pretty.

/Tomas
 Message: Posted by: glowball (Nov 27, 2018 11:04AM)
No, these are great!
They all require a group of five ones and fives zeros this is fine.
They all have a group of four ones and four zeros this is also fine but I like to keep the groups further away from each other to make the initial spread look good. The fourth debruin in your above list is especially good in this regard and I will use it (the tenth deBruijn in your first post was also very good in this regard).

Note that I will have the first two cards cut to the bottom by me ahead of time to help break up the initial view so there won't be 5 red cards in a row during the initial spread.
Thanks!
 Message: Posted by: glowball (Nov 28, 2018 12:00PM)
Tomas, (or anyone out there) do you know if Leo Boudreau's 52 bit debruin published in his Spirited Pasteboards book is the first published 52 bit DeBruijn? If so I would like for him to get recognition for that.
 Message: Posted by: glowball (Dec 4, 2018 01:48PM)
To all,
Just to clarify, the below is the complete list of 26-26 DeBruijn's from Tomas. I will start using R2 Below.

A. 1111110010101101100110100100111011100000010001100010
B. 1111110111100101001101000010010001110101011000001100
C. 1111110111010001111000100000011001001101011011000010
D. 1111110101111001011010000110001110111000000100010100
E. 1111110111010100000110010001011011000010010101111000
F. 1111110000101100011010011001010100010000011110101110
G. 1111110111010110000101111000100000011010010100011100
H. 1111101000011000001000101101010010101110011110001110
I. 1111100101000111101001100111000010000011011101100010
J. 1111101100001001101111001011101011010001010100100000
K. 1111100001001000001100110100111001010001111010101110
L. 1111100001001101011110111001011001110100010100100000
M. 1111100000111001100011011010000101100100101010011110
N. 1111101010110010011000000110111011010010100011100010

O. 1111101011110011001010010011100001011011000110100000
P. 1111101010110011000101110111100100101001110000100000
Q. 1111101001010110011101101110010011000110101000100000
R1. 1111101000110011101111001001101100001010111000100000
R2. 1110100011001110111100100110110000101011100010000011
S. 1111101110010011001110101111000100001010001101100000
T. 1111101110010011010110011101001010001011110000100000
U. 1111100110110001000110010011101000010101111011100000
V. 1111100111010010000100110010101000101111011011100000
W. 1111100010001100100110101011011110110000101110100000
X. 1111100001011100110010100011010101101111011000100000
Y. 1111100001000101100011010100101011110111001110100000
Note that R1 and R2 are the same (just a different starting point).
 Message: Posted by: glowball (Dec 7, 2018 03:35AM)
Actually I'm going to use a variant of the "P" deBruijn because I can quickly construct it from an existing Aronson deck.

This physical Deck is:
Js Kc 5c 2h 9s 3h 6c 8d Ac 10s 5h 2d As 3s Ad Kd 7d 8c Ah 8s 7s 5S Qd Jc 9c Qs 10c Jh 8H 4s 10h 6h 3c Jd 2s 9h 9d Ks 6s 4c 3d 7h Qh 5d 7c 4h Kh 4d 10d 6d Qc 2c

The 8 step instructions on how to create the deck from an existing Aronson deck and the Sorted Crib Sheet for it can be found at the link below:
https://www.themagiccafe.com/forums/viewtopic.php?topic=680765&forum=99
 Message: Posted by: glowball (Dec 12, 2018 01:28PM)
For those interested here are the P3 DeBruijn bits:
0001010100110011101000100001101101011000111101111100

Below is the "cheat sheet" for the above mentioned physical deck ending with the 2C:
SORTED (for fast human lookup) Crib Sheet
for TomasB's P3 DeBruijn and glowball's cards:

01=8s 7s 5S Qd Jc 9c
02=2c Js Kc 5c 2h 9s
03=9c Qs 10c Jh 8h 4s
04=Qc 2c Js Kc 5c 2h
05=Js Kc 5c 2h 9s 3h
06=Jc 9c Qs 10c Jh 8h
07=Ks 6s 4c 3d 7h Qh
10=6d Qc 2c Js Kc 5c
12=Ah 8s 7s 5S Qd Jc
13=8d Ac 10s 5h 2d As
14=Qd Jc 9c Qs 10c Jh
16=9d Ks 6s 4c 3d 7h
17=2d As 3s Ad Kd 7d
20=5S Qd Jc 9c Qs 10c
21=9s 3h 6c 8d Ac 10s
23=3c Jd 2s 9h 9d Ks
24=8c Ah 8s 7s 5S Qd
25=5c 2h 9s 3h 6c 8d
26=6c 8d Ac 10s 5h 2d
30=10d 6d Qc 2c Js Kc
31=Kd 7d 8c Ah 8s 7s
33=Jh 8h 4s 10h 6h 3c
34=9h 9d Ks 6s 4c 3d
35=10h 6h 3c Jd 2s 9h
36=5h 2d As 3s Ad Kd
37=Qh 5d 7c 4h Kh 4d
40=7s 5S Qd Jc 9c Qs
41=Ac 10s 5h 2d As 3s
42=Kc 5c 2h 9s 3h 6c
43=As 3s Ad Kd 7d 8c
45=Qs 10c Jh 8h 4s 10h
47=6s 4c 3d 7h Qh 5d
50=7d 8c Ah 8s 7s 5S
51=Jd 2s 9h 9d Ks 6s
52=2h 9s 3h 6c 8d Ac
54=3h 6c 8d Ac 10s 5h
55=8H 4s 10h 6h 3c Jd
56=6h 3c Jd 2s 9h 9d
57=5d 7c 4h Kh 4d 10d
60=2s 9h 9d Ks 6s 4c
62=4s 10h 6h 3c Jd 2s
63=4c 3d 7h Qh 5d 7c
64=10s 5h 2d As 3s Ad
65=3s Ad Kd 7d 8c Ah
66=10c Jh 8h 4s 10h 6h
67=7c 4h Kh 4d 10d 6d
70=4d 10d 6d Qc 2c Js
71=Kh 4d 10d 6d Qc 2c
72=Ad Kd 7d 8c Ah 8s
73=4h Kh 4d 10d 6d Qc
75=3d 7h Qh 5d 7c 4h
76=7h Qh 5d 7c 4h Kh

glowball yelnif
 Message: Posted by: glowball (Dec 12, 2018 08:04PM)
Tomas I have two questions:
1. What is the longest (6 bit sequence) DeBruijn string that only utilizes 4 "0"s or less and 4 "1"s or less (no 000000 nor 00000 nor 111111 nor 11111)? I'm guessing maybe a 27 bit debruin?

2. What deBruijn do you know of that closest approximates the below bit string:
Below line is the Aronson red cards as "1"s:
0001001010011110010011011110111101010110010001001001

If either of the above questions takes a long time just ignore it but thanks for all your help either way.

global yelnif
 Message: Posted by: jmbulg (Dec 14, 2018 05:00PM)
[quote]On Dec 12, 2018, glowball wrote:
Tomas I have two questions:
1. What is the longest (6 bit sequence) DeBruijn string that only utilizes 4 "0"s or less and 4 "1"s or less (no 000000 nor 00000 nor 111111 nor 11111)? I'm guessing maybe a 27 bit debruin?

2. What deBruijn do you know of that closest approximates the below bit string:
Below line is the Aronson red cards as "1"s:
0001001010011110010011011110111101010110010001001001

If either of the above questions takes a long time just ignore it but thanks for all your help either way.

global yelnif [/quote]

You mean something as

1)

1, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0
or
1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0

2)

depends on what you call "closest". Least number if single bit displacement, least number of block displacements, least number of running x cards , ...

JM

PS: Sorry Tomas, this one I won ;-)
 Message: Posted by: jmbulg (Dec 14, 2018 05:35PM)
BTW, the two sequences are cyclic, you can cut wherever you want..
 Message: Posted by: glowball (Dec 15, 2018 02:44AM)
Jmbulg,
this is great!

1. To make an "Eyes closed if your card is red" deck where there would never be 5 or more eyes closed (or 5 or more eyes open). I think it looks a lot better if there is good mixture between red cards and black cards among the 6 cards and when doing the initial spread of all the cards.

Your response satisfies that purpose big time!

2. To see how few steps it would take to convert an Aronson deck to a full 52 bit de Bruijn deck (based on hearts and diamonds being binary "1"). For that purpose a group approach is probably best (I have reduced the steps to 5 so far using what I call the "P" de Bruijn from Tomas).
Also am thinking about how much I could keep the Aronson sequences intact (or close by) in the resulting de Bruijn deck.

This is great info. Thanks again so much!

glowball yelnif
 Message: Posted by: glowball (Dec 17, 2018 08:37PM)
Jmbulg,

I was wrongly thinking that a 4 bit max would mean no 5 cards would be the same color (red or black) in the 6 card group.
Although it is true for 5 contiguous cards but I forgot about situations like 010000, 001000, 111101, 111011 non contiguous strings.

I'm naming your two de Bruijns JM1 and JM2.

I analyzed JM1 and JM2 for their 52 6 bit sequences and found that they each have 8 occurrences of 5 like bits (8/52 = 15%).
I analyzed TomasB's P4 for its 52 6 bit sequences and found that it has 10 occurrences of 5 like bits (10/52 = 19%).

This means that 15% of the time when using JM1 or JM2 the spectator will cut/select 6 cards where 5 cards are the same color (red or black).
This means that 19% of the time when using P4 that 5 cards will be the same color.

So JM1 and JM2 are slightly better than P4 in this regard however it only takes 5 steps to convert Aronson to P4 whereas it takes 6 steps to convert Aronson to JM therefore since I have a lot of time and write-ups invested in P4 already, I'll probably stick with P4 for now but am willing to look at more.

Thanks.

glowball yelnif
 Message: Posted by: jmbulg (Dec 19, 2018 01:57AM)
With this different criterium, I found the following cyclic stacks (did not check if they are just the same cycle cut at a different place)

1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1

0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0

1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1

0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1

1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1

0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0

0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0

0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0

They all have only four occurences of five or more identical colors only, sometimes concentrated in a specific part of the stack (you could try to avoid)
 Message: Posted by: glowball (Dec 20, 2018 11:56PM)
Right.
100000 000001 011111 111110

4/52 is about 8 percent of the time they will have 5 cards the same color. Not bad, not bad at all!

8% is a lot better than 19% (which is undesirable, but not a deal breaker either way).

I'm enticed to switch to one of these, but still need to see how many moves to convert Aronson to one of these. Will work on that after Christmas.

Thanks again!

glowball yelnif
 Message: Posted by: Bill Hallahan (May 9, 2020 09:17PM)
In 2018, I wrote software to generate all possible De Bruijn sequences with certain attributes. I found there are more De Bruijn sequences with length 52 that have 26 "one" bits than there are sequences with 28 "one" bits. All comments below refer to a length of 52 bits.

--------------------

There are 731,929,536 De Bruijn sequences with 26 "one" bits.

Those are the 52 rotations of 14,075,568 different sequences.

Since the sequences can run forward or reverse, there are 7,037,784 unique sequences.

--------------------

There are 269,488,128 De Bruijn sequences with 28 "one" bits.

Those are the 52 rotations of 5,182,464 different sequences.

Since the sequences can run forward or reverse, there are 2,591,232 unique sequences.

--------------------

I'm not sure of the proper terminology. I've been calling them bracelet codes. I've seen that term used in magic literature. I think that binary De Bruijn sequences have to be a length that is a power of two. I'm not sure of that though.
 Message: Posted by: bobmag56 (May 10, 2020 08:01AM)
I have a BS in Math and MS in Computer Science and find this posting very interesting. However, seems somewhat complex from a performance view.