大家做做这个

STEM版,合并数学,物理,化学,科学,工程,机械。不包括生物、医学相关,和计算机相关内容。

版主: verdeliteTheMatrix

混元形意太极门(掌门人)
职业作家
职业作家
帖子互动: 34
帖子: 728
注册时间: 2022年 12月 20日 14:53

Re: 大家做做这个

帖子 混元形意太极门(掌门人) »

可以想象成在Z_(2N-1) 里操作。每次操作都是 f(x)=2x-1.
k 次操作以后就是2^kx-2^k+1.
根据欧拉定理2^m=1(mod 2N-1) 当 m 为与 2N-1互素的个数。
得证。

(ヅ) 写了: 2023年 1月 22日 16:57 是,问题实际上是,为什么不会拆成1+7+3+1这种
x1 图片
老将皆傻逼;煤粉皆球盲。
FoxMe(令狐)
论坛精英
论坛精英
帖子互动: 144
帖子: 5330
注册时间: 2022年 7月 26日 16:46

Re: 大家做做这个

帖子 FoxMe(令狐) »

上次由 FoxMe 在 2023年 1月 23日 13:19 修改。
头像
YWY(夜未央)
论坛支柱
论坛支柱
2023-24年度十大优秀网友
帖子互动: 1263
帖子: 13846
注册时间: 2022年 7月 22日 17:25

Re: 大家做做这个

帖子 YWY(夜未央) »

CalCat 写了: 2023年 1月 23日 12:32 Look up Faro Shuffle on Wikipedia.
赞!
持仓抄底锁利,你钱你定
看牛观猪喊熊,自娱自乐
股市变幻莫测,不作不死
赌途曲折无常,吃枣药丸
FoxMe(令狐)
论坛精英
论坛精英
帖子互动: 144
帖子: 5330
注册时间: 2022年 7月 26日 16:46

Re: 大家做做这个

帖子 FoxMe(令狐) »

混元形意太极门 写了: 2023年 1月 23日 13:14 可以想象成在Z_(2N-1) 里操作。每次操作都是 f(x)=2x-1.
k 次操作以后就是2^kx-2^k+1.
根据欧拉定理2^m=1(mod 2N-1) 当 m 为与 2N-1互素的个数。
得证。
2的阶数是phi(2N-1)的因子,那么最多phi(2N-1)<=2N-2次洗牌就回到初始状态。这里phi(2N-1)是{1,2,..,2N-1}中与2N-1互素的整数的个数。还是群论。

N=4, phi(7)=6
N=5, phi(9)=6
N=6, phi(11)=10
N=7, phi(13)=12

都能对得上。2N-2次比2N次稍微改进了一点。
头像
(ヅ)楼主
论坛支柱
论坛支柱
帖子互动: 544
帖子: 11677
注册时间: 2022年 8月 21日 14:20

Re: 大家做做这个

帖子 (ヅ)楼主 »

混元形意太极门 写了: 2023年 1月 23日 13:14 可以想象成在Z_(2N-1) 里操作。每次操作都是 f(x)=2x-1.
k 次操作以后就是2^kx-2^k+1.
根据欧拉定理2^m=1(mod 2N-1) 当 m 为与 2N-1互素的个数。
得证。
正确!这样可以得到一个resetting shuffle的上界2N-2

提供另外一种思路:
考虑2^1, 2^2,..., 2^{2N} mod 2N-1
必然有两个1 <= i < j <= 2N相同
2^i = 2^j mod 2N - 1
那么2^{j-i} = 1 mod 2N-1 (2^i 跟2N-1互质,所以其逆存在)
上次由 (ヅ) 在 2023年 1月 23日 20:36 修改。
头像
(ヅ)楼主
论坛支柱
论坛支柱
帖子互动: 544
帖子: 11677
注册时间: 2022年 8月 21日 14:20

Re: 大家做做这个

帖子 (ヅ)楼主 »

补充一问,根据混元形意太极门的解可知2N-2次洗牌可以使得牌洗回原样,2N-2为最小resetting shuffle的上界。那么使得需要最少洗2N-2次才能还原的条件是什么(in terms of N).

请给出一个充分条件或者必要条件
头像
YWY(夜未央)
论坛支柱
论坛支柱
2023-24年度十大优秀网友
帖子互动: 1263
帖子: 13846
注册时间: 2022年 7月 22日 17:25

Re: 大家做做这个

帖子 YWY(夜未央) »

(ヅ) 写了: 2023年 1月 23日 17:36 补充一问,根据混元形意太极门的解可知2N-2次洗牌可以使得牌洗回原样,2N-2为最小resetting shuffle的上界。那么使得需要最少洗2N-2次才能还原的条件是什么(in terms of N).

请给出一个充分条件或者必要条件
这就是primitive root的问题。如果是mod 2N-1的话,因为限定在奇数范围内,有primitive root的充要条件是2N-1等于一个奇素数的方幂。所以2是primitive root mod 2N-1的必要条件是N = (p^n+1)/2 where p is an odd prime。充分条件不清楚,但很多情况下2都是primitive root mod p^n。等看大家的回答。
持仓抄底锁利,你钱你定
看牛观猪喊熊,自娱自乐
股市变幻莫测,不作不死
赌途曲折无常,吃枣药丸
头像
YWY(夜未央)
论坛支柱
论坛支柱
2023-24年度十大优秀网友
帖子互动: 1263
帖子: 13846
注册时间: 2022年 7月 22日 17:25

Re: 大家做做这个

帖子 YWY(夜未央) »

(ヅ) 写了: 2023年 1月 23日 17:36 补充一问,根据混元形意太极门的解可知2N-2次洗牌可以使得牌洗回原样,2N-2为最小resetting shuffle的上界。那么使得需要最少洗2N-2次才能还原的条件是什么(in terms of N).

请给出一个充分条件或者必要条件
YWY 写了: 2023年 1月 23日 18:12 这就是primitive root的问题。如果是mod 2N-1的话,因为限定在奇数范围内,有primitive root的充要条件是2N-1等于一个奇素数的方幂。所以2是primitive root mod 2N-1的必要条件是N = (p^n+1)/2 where p is an odd prime。充分条件不清楚,但很多情况下2都是primitive root mod p^n。等看大家的回答。
需要最少洗2N-2次才能还原的必要条件是N = (p+1)/2 where p is an odd prime,因为2N-1必须等于一个奇素数。
持仓抄底锁利,你钱你定
看牛观猪喊熊,自娱自乐
股市变幻莫测,不作不死
赌途曲折无常,吃枣药丸
头像
(ヅ)楼主
论坛支柱
论坛支柱
帖子互动: 544
帖子: 11677
注册时间: 2022年 8月 21日 14:20

Re: 大家做做这个

帖子 (ヅ)楼主 »

YWY 写了: 2023年 1月 23日 18:12 这就是primitive root的问题。如果是mod 2N-1的话,因为限定在奇数范围内,有primitive root的充要条件是2N-1等于一个奇素数的方幂。所以2是primitive root mod 2N-1的必要条件是N = (p^n+1)/2 where p is an odd prime。充分条件不清楚,但很多情况下2都是primitive root mod p^n。等看大家的回答。
有一个反例
p = 7, n = 1, N = 4, 2N-1 = 7
2不是primitive root mod 7

算了一下小于100的质数,有不少2都不是primitive root mod p

代码: 全选

2 is NOT primitive root modulo 7
2 is NOT primitive root modulo 17
2 is NOT primitive root modulo 23
2 is NOT primitive root modulo 31
2 is NOT primitive root modulo 41
2 is NOT primitive root modulo 43
2 is NOT primitive root modulo 47
2 is NOT primitive root modulo 71
2 is NOT primitive root modulo 73
2 is NOT primitive root modulo 79
2 is NOT primitive root modulo 89
2 is NOT primitive root modulo 97
头像
(ヅ)楼主
论坛支柱
论坛支柱
帖子互动: 544
帖子: 11677
注册时间: 2022年 8月 21日 14:20

Re: 大家做做这个

帖子 (ヅ)楼主 »

YWY 写了: 2023年 1月 23日 18:47 需要最少洗2N-2次才能还原的必要条件是N = (p+1)/2 where p is an odd prime,因为2N-1必须等于一个奇素数。
这个必要条件也不太对,

N = 4, p = 7就只需要shuffle 3次
头像
YWY(夜未央)
论坛支柱
论坛支柱
2023-24年度十大优秀网友
帖子互动: 1263
帖子: 13846
注册时间: 2022年 7月 22日 17:25

Re: 大家做做这个

帖子 YWY(夜未央) »

(ヅ) 写了: 2023年 1月 23日 20:05 有一个反例
p = 7, n = 1, N = 4, 2N-1 = 7
2不是primitive root mod 7

算了一下小于100的质数,有不少2都不是primitive root mod p

代码: 全选

2 is NOT primitive root modulo 7
2 is NOT primitive root modulo 17
2 is NOT primitive root modulo 23
2 is NOT primitive root modulo 31
2 is NOT primitive root modulo 41
2 is NOT primitive root modulo 43
2 is NOT primitive root modulo 47
2 is NOT primitive root modulo 71
2 is NOT primitive root modulo 73
2 is NOT primitive root modulo 79
2 is NOT primitive root modulo 89
2 is NOT primitive root modulo 97
2是primitive root mod p 的必要条件是 p = 3 or 5 mod 8。
持仓抄底锁利,你钱你定
看牛观猪喊熊,自娱自乐
股市变幻莫测,不作不死
赌途曲折无常,吃枣药丸
头像
YWY(夜未央)
论坛支柱
论坛支柱
2023-24年度十大优秀网友
帖子互动: 1263
帖子: 13846
注册时间: 2022年 7月 22日 17:25

Re: 大家做做这个

帖子 YWY(夜未央) »

(ヅ) 写了: 2023年 1月 23日 20:42 这个必要条件也不太对,

N = 4, p = 7就只需要shuffle 3次
所以我说是必要条件,但不充分。
持仓抄底锁利,你钱你定
看牛观猪喊熊,自娱自乐
股市变幻莫测,不作不死
赌途曲折无常,吃枣药丸
头像
(ヅ)楼主
论坛支柱
论坛支柱
帖子互动: 544
帖子: 11677
注册时间: 2022年 8月 21日 14:20

Re: 大家做做这个

帖子 (ヅ)楼主 »

YWY 写了: 2023年 1月 23日 20:44 所以我说是必要条件,但不充分。
我想想,这整糊涂了
头像
(ヅ)楼主
论坛支柱
论坛支柱
帖子互动: 544
帖子: 11677
注册时间: 2022年 8月 21日 14:20

Re: 大家做做这个

帖子 (ヅ)楼主 »

YWY 写了: 2023年 1月 23日 20:43 2是primitive root mod p 的必要条件是 p = 3 or 5 mod 8。
prm37里面有2
头像
YWY(夜未央)
论坛支柱
论坛支柱
2023-24年度十大优秀网友
帖子互动: 1263
帖子: 13846
注册时间: 2022年 7月 22日 17:25

Re: 大家做做这个

帖子 YWY(夜未央) »

(ヅ) 写了: 2023年 1月 23日 20:46 我想想,这整糊涂了
所以说,你上面举得p =7, 17, 23, 31, 41, 43等等只说明它们不充分,但不反证我说的必要条件。

同样,2是primitive root mod p 的必要条件是 p = 3 or 5 mod 8。但p = 43不是反例,只说明p = 3 or 5 mod 8不是充分条件。
持仓抄底锁利,你钱你定
看牛观猪喊熊,自娱自乐
股市变幻莫测,不作不死
赌途曲折无常,吃枣药丸
头像
YWY(夜未央)
论坛支柱
论坛支柱
2023-24年度十大优秀网友
帖子互动: 1263
帖子: 13846
注册时间: 2022年 7月 22日 17:25

Re: 大家做做这个

帖子 YWY(夜未央) »

(ヅ) 写了: 2023年 1月 23日 21:00 prm37里面有2
37 = 5 mod 8,不矛盾。
持仓抄底锁利,你钱你定
看牛观猪喊熊,自娱自乐
股市变幻莫测,不作不死
赌途曲折无常,吃枣药丸
头像
(ヅ)楼主
论坛支柱
论坛支柱
帖子互动: 544
帖子: 11677
注册时间: 2022年 8月 21日 14:20

Re: 大家做做这个

帖子 (ヅ)楼主 »

YWY 写了: 2023年 1月 23日 21:02 37 = 5 mod 8,不矛盾。
我有两个疑问

1. "2是primitive root mod 2N-1的必要条件是N = (p^n+1)/2 where p is an odd prime"这是正确的,但是没想通跟"requires 2N-2 shuffles to reset deck"有什么关系

对于任意N,都存在k 使得2^k = 1 mod 2N - 1

2. "需要最少洗2N-2次才能还原的必要条件是N = (p+1)/2 where p is an odd prime,因为2N-1必须等于一个奇素数。"

这个是怎么得到?
头像
YWY(夜未央)
论坛支柱
论坛支柱
2023-24年度十大优秀网友
帖子互动: 1263
帖子: 13846
注册时间: 2022年 7月 22日 17:25

Re: 大家做做这个

帖子 YWY(夜未央) »

(ヅ) 写了: 2023年 1月 24日 00:31 我有两个疑问

1. "2是primitive root mod 2N-1的必要条件是N = (p^n+1)/2 where p is an odd prime"这是正确的,但是没想通跟"requires 2N-2 shuffles to reset deck"有什么关系

对于任意N,都存在k 使得2^k = 1 mod 2N - 1
2. "需要最少洗2N-2次才能还原的必要条件是N = (p+1)/2 where p is an odd prime,因为2N-1必须等于一个奇素数。"

这个是怎么得到?
没有直接关系但又间接关系。“2是primitive root mod 2N-1”是说需要至少phi(2N-1)次(欧拉数)才能还原。注意phi(2N-1)小于等于2N-2。所以,“需要最少洗2N-2次才能还原”的充要条件是“phi(2N-1) = 2N-2而且2是primitive root mod 2N-1”。但phi(2N-1) = 2N-2当且仅当2N-1等于一个奇素数。所以“需要最少洗2N-2次才能还原”的充要条件是“2N-1是奇素数而且2是primitive root mod 2N-1”。这样,“N = (p+1)/2 where p is an odd prime”是必要条件,“2是primitive root mod 2N-1”也是必要条件。还有,通过考虑二次剩余,“2是primitive root mod p”的必要条件是“p = 3 or 5 mod 8”。所以“需要最少洗2N-2次才能还原”的必要条件是“N = (p+1)/2 where p is an odd prime and p = 3 or 5 mod 8”。
x1 图片
持仓抄底锁利,你钱你定
看牛观猪喊熊,自娱自乐
股市变幻莫测,不作不死
赌途曲折无常,吃枣药丸
头像
(ヅ)楼主
论坛支柱
论坛支柱
帖子互动: 544
帖子: 11677
注册时间: 2022年 8月 21日 14:20

Re: 大家做做这个

帖子 (ヅ)楼主 »

YWY 写了: 2023年 1月 24日 00:54 没有直接关系但又间接关系。“2是primitive root mod 2N-1”是说需要至少phi(2N-1)次(欧拉数)才能还原。注意phi(2N-1)小于等于2N-2。所以,“需要最少洗2N-2次才能还原”的充要条件是“phi(2N-1) = 2N-2而且2是primitive root mod 2N-1”。但phi(2N-1) = 2N-2当且仅当2N-1等于一个奇素数。所以“需要最少洗2N-2次才能还原”的充要条件是“2N-1是奇素数而且2是primitive root mod 2N-1”。这样,“N = (p+1)/2 where p is an odd prime”是必要条件,“2是primitive root mod 2N-1”也是必要条件。还有,通过考虑二次剩余,“2是primitive root mod p”的必要条件是“p = 3 or 5 mod 8”。所以“需要最少洗2N-2次才能还原”的必要条件是“N = (p+1)/2 where p is an odd prime and p = 3 or 5 mod 8”。
我还是不明白“2是primitive root mod 2N-1”是说需要至少phi(2N-1)次(欧拉数)才能还原“的原因 :oops:

白天再仔细想想
头像
YWY(夜未央)
论坛支柱
论坛支柱
2023-24年度十大优秀网友
帖子互动: 1263
帖子: 13846
注册时间: 2022年 7月 22日 17:25

Re: 大家做做这个

帖子 YWY(夜未央) »

(ヅ) 写了: 2023年 1月 24日 01:35 我还是不明白“2是primitive root mod 2N-1”是说需要至少phi(2N-1)次(欧拉数)才能还原“的原因 :oops:

白天再仔细想想
这就是“2是primitive root mod 2N-1”的定义,就是说2至少要phi(2N-1)次幂才等于1 mod 2N-1。注意2的phi(2N-1)次幂肯定等于1 mod 2N-1(欧拉定理),这是你一楼洗牌题证明的关键。
持仓抄底锁利,你钱你定
看牛观猪喊熊,自娱自乐
股市变幻莫测,不作不死
赌途曲折无常,吃枣药丸
回复

回到 “STEM”