Shift Equivalency

davar55 · 2008-06-19, 21:33

Consider the set of B^N N-digit numbers in base B, with lead zeros
being significant. Call two such numbers "shift-equivalent" if one can
be mapped to the other by a rotation or a reversal of a rotation.
This partitions the set into equivalence classes, each of which can
contain at most 2N elements.

For example, with B=10 and N=4, these are some equivalence classes:

{1357,3571,5713,7135,7531,5317,3175,1753},
{1111},
{1122,1221,2211,2112},
{1313,3131}

For B=N=10, two problems:

Compute the number of equivlence classes.
Exhibit an equivalence class with a maximal number of primes.

maxal · 2008-07-21, 21:19

The number of equivalent classes is easy to compute with PET.

nibble4bits · 2008-07-24, 00:54

Haha this reminds of the days of the Apple 2's disk formats. They used values like 5A5A5... to mark bounderies so that the drive controller's firmware could translate (in real time) the raw bits into bytes. The idea was that since it's easy to do a compare of one byte to another, they saved the time of doing the shift until the actual translation. Thus they didn't make the 6502 processor go through a rather larger search space in comparison. For practical reasons, they would have had to read the track many times until it just lined up perfect.

Thanks for reminding me of the math that actually lead up to Wozniak's reasoning for the firmware's algorythm.

Rotations, binary inversions (NOT), directional inversions (high bit for low bit), and additions/XOR give quite a large set of results for a specific initial value.

davar55 · 2009-07-02, 19:27

Has anyone tried this yet?

Remember the relationship between equivalence classes and partitions.

2008-06-19, 21:33	#1
davar55 May 2004 New York City 5·7·11² Posts	Shift Equivalency Consider the set of B^N N-digit numbers in base B, with lead zeros being significant. Call two such numbers "shift-equivalent" if one can be mapped to the other by a rotation or a reversal of a rotation. This partitions the set into equivalence classes, each of which can contain at most 2N elements. For example, with B=10 and N=4, these are some equivalence classes: {1357,3571,5713,7135,7531,5317,3175,1753}, {1111}, {1122,1221,2211,2112}, {1313,3131} For B=N=10, two problems: Compute the number of equivlence classes. Exhibit an equivalence class with a maximal number of primes.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Residue and Shift, what do these mean?	king	Information & Answers	1	2018-03-05 05:52
Shift Number in LL Test	Kalli Hofmann	Information & Answers	1	2018-01-08 12:24
How does the random shift work?	CuriousKit	Math	9	2016-01-16 00:33
Why different shift counts are important	Madpoo	Data	6	2015-10-11 03:55
Alt codes : should shift = +32 in them ?	science_man_88	Programming	13	2011-06-24 06:52

2008-07-21, 21:19	#2
maxal Feb 2005 2²×5×13 Posts	The number of equivalent classes is easy to compute with PET.

2008-07-24, 00:54	#3
nibble4bits Nov 2005 2×7×13 Posts	Haha this reminds of the days of the Apple 2's disk formats. They used values like 5A5A5... to mark bounderies so that the drive controller's firmware could translate (in real time) the raw bits into bytes. The idea was that since it's easy to do a compare of one byte to another, they saved the time of doing the shift until the actual translation. Thus they didn't make the 6502 processor go through a rather larger search space in comparison. For practical reasons, they would have had to read the track many times until it just lined up perfect. Thanks for reminding me of the math that actually lead up to Wozniak's reasoning for the firmware's algorythm. Rotations, binary inversions (NOT), directional inversions (high bit for low bit), and additions/XOR give quite a large set of results for a specific initial value.

2009-07-02, 19:27	#4
davar55 May 2004 New York City 4235₁₀ Posts	Has anyone tried this yet? Remember the relationship between equivalence classes and partitions.