Polite Number
 

เรื่อง Politeness ของจำนวน
An easy way of calculating the politeness of a positive number is that of decomposing the number into its prime factors, taking the powers of all prime factors greater than 2, adding 1 to all of them, multiplying the numbers thus obtained with each other and subtracting 1.
จาก Wikipedia
ผมอยากรู้ว่าจะพิสูจน์ได้ยังไงครับ
ส่วนเรื่องนิยามก็ตามของ Polite Number นะครับ

จากนิยาม
polite number ของ $a$ ($a \in \mathbb{N}$) จะเท่ากับ $\mid \left\{ (n,k) \in \mathbb{N}^2 \mid a = n+(n+1)+\cdots + (n+k) \right\} \mid$

แก้สมการ

...

จะได้ว่าเราต้องหาจำนวนคำตอบของ $2a = (2n+k)(1+k)$

ต่อมาสมมติว่า $(n,k)$ เป็นคำตอบของสมการดังกล่าว และ $A = 2n+k, B=1+k$

ให้ $2a = 2^{i_0}p_1^{i_1} \cdots p_j^{i_j} = AB$

จะได้ว่า $n= \frac{A-B+1}{2}, k = B-1$

นั่นคือ $(n,k)$ จะเป็นคำตอบได้ $(A,B)$ ต้องสอดคล้องกับ
1. $A>B$
2. $A-B$ เป็นเลขคี่
3. $B>1$

จากเงื่อนไข 2.
จะได้ว่า $A = 2^{i_0}p_1^{l_1} \cdots p_j^{l_j}, B = p_1^{i_1-l_1} \cdots p_j^{i_j-l_j}$ __(3)
หรือ $ฺB = 2^{i_0}p_1^{l_1} \cdots p_j^{l_j}, A = p_1^{i_1-l_1} \cdots p_j^{i_j-l_j}$ __(4)

แต่จากเงื่อนไข 1. $A$ ต้องเป็นจำนวนที่มากกว่า แต่ละ $(l_1,l_2,...,l_j)$ จะเกิดได้แค่ (3) หรือ (4) อันใดอันนึงเท่านั้น

ดังนั้นแต่ละ $(l_1,l_2,...,l_j)$ จะมี $(A,B)$ แค่คำตอบเดียว และจะมี $(n,k)$ แค่คำตอบเดียว
(ในทางกลับกัน $(n,k)$ คำตอบเดียวก็จะมี $(l_1,l_2,...,l_j)$ แค่คำตอบเดียวด้วยเช่นกัน)

จึงเกิด bijection ของ $(n,k)$ และ $(l_1,l_2,...,l_j)$

จำนวนคำตอบ $(n,k)$ จะเท่ากับจำนวนของ $(l_1,l_2,...,l_j)$ เท่ากับ $(l_1+1)(l_2+1) \cdots (l_j+1)$

ตัดกรณีที่ $(A,B) = (2n,1)$ ออก (เงื่อนไข 3.) จำนวนคำตอบ $(n,k)$ จะเท่ากับ $(l_1+1)(l_2+1) \cdots (l_j+1)-1$