首页 > 其他分享 >根据筛法规则对整数分类,建立树状结构

根据筛法规则对整数分类,建立树状结构

时间:2024-02-03 21:12:32浏览次数:28  
标签:结点 右子 筛法 树状 元素 整数 素数

筛法目前一般用来找整数序列中的素数,不是素数的元素被丢掉了。如果仅把筛法当成一种分类规则,把筛掉的元素和留下的元素算作不同的分类,并用每一类中的最小元素递归地执行筛法,那么能把所有正整数保留下来,并建立一个树状结构。
例如,初始集合是正整数集,根据模最小元素p是否为0,可把所有元素分成两类,递归地执行下去,得到如下图像:

容易观察到的一些规律:
(1)左子链是素数集;假设结点\(v\)的最大素因子是第i个素数\(p_i\),则结点\(v\)的右子链是公比为\(p_i\)的等比数列;
(2)从2开始的整个树是完全二叉树,结点\(v\)的最大素因子是\(p_i\)时,\(v\)的左子结点是是\(\frac{p_{i+1}}{p_i}v\),右子节点是\(vp_i\),父节点是\(\frac{p_{i-1}}{p_i}v\);
(3)树\(v\)的右子树与树\(v\)同构,只是元素乘了个系数\(p_i\);这说明此树具有简单的分形性质,一切基于左子链的素数集。本文所有结点\(v\)的右子树都是\(\mod v=0\)的元素那个分支。

以上是模最小元素p是否为0进行2分类生成的树,更进一步,假设集合的最小元素是\(p\),所有数字根据模\(p\)的结果分成\(p\)个同余类,产生\(p\)个子树,生成的树状图如下:

此树状结构里,素数的分布不再有规律,但仍然具有拓扑性质(3),这解释了合数\(v\)的子节点数量为什么不是\(v\),而是\(v\)的最大素因数\(p_i\)。

这种模\(p\)分类树的分形性质感觉跟欧拉乘积公式\(\sum_{n=1}^\infty\frac{1}{n^s}=\prod_p\frac{1}{1-p^{-s}}\)有点关系,反正都是筛法的思想;不知道此树状图是否有助于一些数论定理的直观表示,或者用来帮助解决哥德巴赫猜想等数论问题?例如第一幅图(模\(p\)二分类树)以结点3为根节点的子树元素是3开始的全部奇数,构成了等差数列,可以利用此树的拓扑性质尝试证明每个奇数都是两个素数的等差中项。

另外,考拉兹猜想等一些问题也涉及把正整数集构造成一颗树,而原来的数轴相当于一根链,是树型拓扑中一种平凡的情况,不知道能否对所有的树型结构,建立一套通用的理论呢?
如果已有研究此问题的学科,不知道属于哪类,几何数论?代数拓扑?图论?组合数学?本人不是数学科班的,所以不了解,有知道的烦请告知一下。

标签:结点,右子,筛法,树状,元素,整数,素数
From: https://www.cnblogs.com/wm27916/p/18004547

相关文章

  • 2024-02-03:用go语言,你有 k 个背包。给你一个下标从 0 开始的整数数组 weights, 其中 we
    2024-02-03:用go语言,你有k个背包。给你一个下标从0开始的整数数组weights,其中weights[i]是第i个珠子的重量。同时给你整数k,请你按照如下规则将所有的珠子放进k个背包。没有背包是空的。如果第i个珠子和第j个珠子在同一个背包里,那么下标在i到j之间的所有珠......
  • 在 C# 中,`int[]`(数组)和 `List<int>`(列表)都可以用来存储一组整数,但它们有一些重要的区
    在C#中,int[](数组)和List<int>(列表)都可以用来存储一组整数,但它们有一些重要的区别:大小:int[]的大小在创建时就确定了,不能改变。而List<int>的大小是动态的,可以添加或删除元素,大小会自动调整¹。方法:List<int>提供了许多方便的方法,如Add、Remove、Insert等,而int[]没有这些方......
  • 【技巧总结】java整数,字符串,数组之间的相互转换(持续更新)
    字符串转换为int类型给定一个字符串Stringstr="1234";转为转数字1234valueOf()Integernum=Integer.valueOf(str);返回的是包装类对象,可以进行调用对象方法可以用toString()方法。​parseIntintnum=Integer.parseInt(str)返回的是基本数据类型字符串......
  • 区间修改,单点查询的树状数组
    #include<bits/stdc++.h>#defineCLOSEios::sync_with_stdio(false);cin.tie(0);cout.tie(0)#defineendl"\n"typedeflonglongLL;constintN=1e6+10,M=N,mod=1e9+7;usingnamespacestd;inta[N],b[N],n,q;LLt[N];intlowbi......
  • 区间修改+区间查询的树状数组
    /*https://www.acwing.com/solution/content/44886/看acwing*/#include<bits/stdc++.h>#defineCLOSEios::sync_with_stdio(false);cin.tie(0);cout.tie(0)#defineendl"\n"typedeflonglongLL;constintN=1e6+10,M=N,mod=1e9+7;u......
  • BigInt:JavaScript 中的任意精度整数
    BigInts 是JavaScript中的一个新的数字基本(primitive)类型,可以用任意精度表示整数。使用 BigInt 可以安全地存储和操作大整数,即使这个数已经超出了 Number 能够表示的安全整数范围。umber 在JavaScript中被表示为双精度浮点数。这意味着它们的精度有限。......
  • 权值树状数组例题——逆序对
    目录问题引入思路一览具体情况code部分补充问题引入(洛谷P1908)[https://www.luogu.com.cn/problem/P1908],简单来说就是给一个数列,求出逆序对的数量思路一览BF做法:遍历数组中的每一个数,对于每一个数,再次遍历前面的数,时间复杂度是n2归并排序:这个...,不太了解,以后明白了再填坑......
  • CSAPP 第二章 信息的表示与处理(1)信息存储与整数表示
    1信息存储机器级程序将内存视为一个非常大的字节数组,成为虚拟内存(virtualmemory)。内存的每个字节都由唯一的数字来标识,称为它的地址(address),所有可能的地址集合就称为虚拟地址空间(virtualaddressspace)。每个程序对象可以简单地视为一个字节块,而程序本身就是一个字节序列。......
  • C语言代码实现:一个整数存储在内存中的二进制中的1的个数
    e.g.代码实现:一个整数存储在内存中的二进制中的1的个数#define_CRT_SECURE_NO_WARNINGS1#include<stdio.h>intmain(){ intnum=0; intcount=0; printf("统计num的补码中有几个1,请输入num:>"); scanf("%d",&num); //统计num的补码中有几个1 //法一 //while(nu......
  • Shell脚本生成随机整数
     Shell脚本生成随机整数$RANDOM:使用当前的进程ID(PID)和当前时间/日期生成的,该时间/日期由自1970年以来经过的秒数定义。 1、urandom命令grep-m1-ao'[0-9]'/dev/urandom|seds/0/10/|head-n1 2、用$RANDOM 要生成范围:{0,..,9} r=$(($RANDOM%10))echo......