將大於2的正整數分解成2個因數（不是質因數），並求其各結果間兩因數最小非負數差，這樣的數有研究的意義嗎？
將大於2的正整數分解成2個因數（不一定是質因數），並求其各結果間兩因數最小非負數差，例如
33=11*3，11-3=8；
36=2*18=3*12=4*9=6*6，取各結果兩因數最小非負數差6-6=0；
（可以知道，平方數的結果肯定是0，而質數的結果肯定比原質數少1）
（我不是數學專業的，不知道數學裡有沒有定義這樣的數，如有，希望告知名稱。）
假設我們可以將其稱作「阿曼數」，並寫作a Aman=X，
比如
………………
33 Aman=8；
34 Aman=15
35 Aman=2
36 Aman=0
37 Aman=36
38 Aman=17
………………
………………
我個人用這樣的數構造密碼，還有其他研究的意義嗎？怎麼用程序求10，000，000以內的「阿曼數」？「阿曼數」的分布有沒有什麼規律？有沒有像「質數螺旋」那樣的特性？
答案有更新！新增了斜率的分析！感謝知友 @Lee Sam！感謝邀請。題主提出的這個數很有意思，我首先編程簡單求解了一下前10000個。（要求解更多的只需要把M換掉就行）
#include &
#include &
int main()
{
//freopen("out.txt","w",stdout);
int i,j,k;
for(i = 2;i &< M;i++)
{
for(j = (int)sqrt(i);j &>= 1;j--)
if((i%j)==0)
{
k = i/j - j;
if(k &< 0) k = -k;
printf("Amon(%d) = %d
",i,k);
break;
}
}
return 0;
}
計算M的阿曼數不會超過sqrt（M）次，因此計算M以內的阿曼數時間複雜度為O(n^1.5)。得到的結果貼在了Ubuntu Pastebin。其中前20個如下：
Amon(2) = 1
Amon(3) = 2
Amon(4) = 0
Amon(5) = 4
Amon(6) = 1
Amon(7) = 6
Amon(8) = 2
Amon(9) = 0
Amon(10) = 3
Amon(11) = 10
Amon(12) = 1
Amon(13) = 12
Amon(14) = 5
Amon(15) = 2
Amon(16) = 0
Amon(17) = 16
Amon(18) = 3
Amon(19) = 18
Amon(20) = 1
好像沒有特別明顯的規律。不過還是可以看出一些特徵：
- 質數p的阿曼數為p-1；
- 完全平方數的阿曼數為0；
- 阿曼數不可能超過本身；
大意如下：a(n)是大於根號n且可以被n整除的最小整數與小於根號n且可以被n整除的最大整數的差。a(n)=0當且僅當n為完全平方數。a(n) is difference between the least divisor of n that is &>= square root(n) and the greatest divisor of n that is &<= square root(n).
a(n) = 0 iff n is a square.
a(n) = n-1 is a new record iff n is a prime number. (End)
For odd n = 2k-1, a(n) = 2*A219695(k) is even. - M. F. Hasler, Nov 25 2012
a(n) = Min{t - d | 0 &< d &<= t &<= n and d*t=n}. - Reinhard Zumkeller, Feb 25 2002
a(n) = A033677(n)-A033676(n). - Omar E. Pol, Jun 21 2009
a(2n-1) = 2*A219695(n). - M. F. Hasler, Nov 25 2012
a(n)=n-1當且僅當n是素數。
當n為奇數時，a(n)=2*A219695 - OEIS,恆為偶數。a(n)是集合{t-d | 0&
#include &
#include &
#define M 10000
double a[M+10];
int cmp(const void *a,const void *b)
{
if(*(double *)a &> *(double *)b) return -1;
else if(*(double *)a &< *(double *)b) return 1;
else return 0;
}
int main()
{
//freopen("out.txt","w",stdout);
int j,k,ii;
ii = 0;
for(int i = 2;i &< M;i++)
{
for(j = (int)sqrt(i);j &>= 1;j--)
if((i%j)==0)
{
k = i/j - j;
if(k &< 0) k = -k;
a[ii++] = (double)k/(double)i;
//printf("Amon(%d) = %d
",i,k);
break;
}
}
qsort(a,M,sizeof(double),cmp);
//for(int i = 2;i &< M;i++) printf("%.4lf ",a[i]);
return 0;
}
求出結果過多，我們將其輸出到文件，再用matlab載入。繪圖如下：
謝邀。 對於任何給定的M 如果N Aman=M 那麼 N 顯然有形式 x(x+M). 反過來 我們可以證明 對x&> =M^2/4 x(x+M) Aman= M.證明如下。 記錄 T= x(x+M) Aman。 那麼T&<=M. 如果T&
計算1-N每個數對應的 阿曼數 可以用普通的篩法，nlogn的複雜度。我想10^7還是可以秒出的。
using System;
namespace Problem51Nod
{
class Program
{
static void Main(string[] args)
{
int max = 10000000;
int[] nums = new int[max + 1];
int sqrt = (int)Math.Sqrt(max);
for (int i = 2; i &<= sqrt; i++) for (int j = i * i; j &<= max; j += i) nums[j] = i; for (int i = 1; i &<= max; i++) { int result = nums[i] == 0 ? i - 1 : i / nums[i] - nums[i]; Console.WriteLine(result); } } } }
amen數的生成是分解因數，很麻煩，而逆運算極其方便，理論上可以用來加密。
但是演算法複雜度只有O(sqrt(n))差的太遠了，離散對數有O(sqrt(n)log(n))呢。。。
個人覺得研究價值可能有，加密應該沒啥了。。。
------------------------------------
但是我突然想到你雖然解密簡單，但是加密也簡單啊。。。所以這個應該是可行的。。。但是這種以分解因數為基礎的加密已經有人做過了，比如rsa就是基於分解因數問題來算的。
我再想一段時間可能有補充。這個和RSA有點像。因為在選取兩個大質數的時候不能兩個數過於接近。比如選取53與59
53*59=3127 在看到3127後因數分解。直接3127^1/2=55.92。。。直接用53作為因數試除發現分解成功。說明這個不是一個好RSA密碼所選取的N。
受到@王希的鼓勵，我也來湊個熱鬧。
先貼個斜率的分布。要說明的是斜率並不是正好在在1/k上，只是正好分部在1/k附近。下圖可以比較好的展現這一點。假設每條直線都穿過原點，並且每個阿曼數都位於一條直線上的話，那麼一個阿曼數所在的直線的斜率則為amon(n)/n,其倒數為n/amon(n):
上圖為每個阿曼數所在的直線的斜率的倒數。可以看出，只有在n足夠大時，斜率才逼近1/k（k為整數）。n不夠大時，斜率實際上是連續而非離散的。
而斜率自身的分布則有點像指數分布（把k開了對數以後）
下面則是安曼數自身的分布。這又有點像另一個指數函數了。
所有質數的阿曼數均為其本身減1
所有平方數的阿曼數均為0
所有相鄰數的積的阿曼數為1
所有平方數減1的阿曼數為2
以上均為充分必要條件。推薦閱讀：
※密碼學如何入門，從什麼方向開始，能推薦書？
※有什麼優秀的有關密碼學的書籍？
※為什麼不能計算兩次哈希，以及在什麼情況下不能計算兩次哈希？
※參加CCBC 併到達終點是什麼感受？
※為什麼CTR模式不是CCA安全的？