mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2008-06-19, 21:33   #1
davar55
 
davar55's Avatar
 
May 2004
New York City

419810 Posts
Default 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.
davar55 is offline   Reply With Quote
Old 2008-07-21, 21:19   #2
maxal
 
maxal's Avatar
 
Feb 2005

22×32×7 Posts
Default

The number of equivalent classes is easy to compute with PET.
maxal is offline   Reply With Quote
Old 2008-07-24, 00:54   #3
nibble4bits
 
nibble4bits's Avatar
 
Nov 2005

B516 Posts
Default

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.
nibble4bits is offline   Reply With Quote
Old 2009-07-02, 19:27   #4
davar55
 
davar55's Avatar
 
May 2004
New York City

2×2,099 Posts
Default

Has anyone tried this yet?

Remember the relationship between equivalence classes and partitions.
davar55 is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 23:45.

Thu Oct 22 23:45:24 UTC 2020 up 42 days, 20:56, 0 users, load averages: 1.72, 1.64, 1.65

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.