【11】整数问题

作者: 备考999天 | 来源:发表于2022-09-03 15:18 被阅读0次

【11】整数问题
随机生成一个长度为 10 的整数类型的数组，例如 [2, 10,
整数划分问题
整数划分问题
整数划分问题
递归--整数划分问题
64位整数问题
LeetCode 386. Lexicographical Nu
Python 14
1016部分A+B

题11.1 已知 $a,b\in \mathbb N_+$ ，求证：
(1) $\frac{b^2}{a^2+ab}$ 不是整数。
(2) 区间 $\left[\frac{b^2}{a^2+ab},\frac{b^2}{a^2+ab-1}\right)$ 中没有整数。

证明 (1) 假设 $\frac{b^2}{a^2+ab}=k$ 是正整数，则关于b的二次方程 $b^2-kab-ka^2=0\\$
有正整数解，这说明 $\Delta =k^2a^2+4ka^2$ 是平方数。
由 $a\in \mathbb N_+$ ，故 $k^2+4k$ 是平方数。
另一方面，因 $k^k<k^2+4k<(k+2)^2$ ，故 $k^2+4k=(k+1)^2$ ，展开移项化简得： $2k=1\\$ 这与 $k$ 是正整数矛盾。所以假设不成立，所以 $\frac{b^2}{a^2+ab}$ 不是整数。
(2) 假设有整数 $k\in \left[\frac{b^2}{a^2+ab},\frac{b^2}{a^2+ab-1}\right)$ ，根据(1)，区间的左端点不为整数，所以：
$\tag{11.1.1} \frac{b^2}{a^2+ab}< k<\frac{b^2}{a^2+ab-1}$
则：
$\frac{b^2}{a^2+ab}< k \Rightarrow \frac{k-\sqrt{k^2+4k}}{2}<\frac{b}a< \frac{k+\sqrt{k^2+4k}}{2}$
$\frac{b^2}{a^2+ab-1}> k \Rightarrow \frac{b}a<\frac{k-\sqrt{k^2+4k(1-1/a^2)}}2$ 或 $\frac{b}a>\frac{k+\sqrt{k^2+4k(1-1/a^2)}}2$
上面不等式合并得：
$\tag{11.1.2}\frac{b}a\in \left[\frac{k-\sqrt{k^2+4k}}{2},\frac{k-\sqrt{k^2+4k(1-1/a^2)}}2\right)$
或
$\tag{11.1.3}\frac{b}a\in \left(\frac{k+\sqrt{k^2+4k(1-1/a^2)}}2,\frac{k+\sqrt{k^2+4k}}2\right)$
(11.1.2)蕴含着 $b/a<0$ ，舍去。
注意到：
$k\le \frac{k+\sqrt{k^2+4k(1-1/a^2)}}2<\frac{k+\sqrt{k^2+4k}}2\le k+1$
故 $k<\frac{b}a< k+1$ ，于是可以作带余除法： $b=ka+r\\r\in\{1,2,...,a-1\}$
将之代入(11.1.1)得：
$\frac{(ka+r)^2}{a^2+a(ka+r)}< k <\frac{(ka+r)^2}{a^2+a(ka+r)-1}\\ \Rightarrow kar+r^2< ka^2<kar+r^2+k\\ \Rightarrow \frac{r^2}{a^2-ar}<k<\frac{r^2}{a^2-ar-1}$
因 $r\in \{1,2,...,a-1\}$ ，令 $a=m+r,m\in\{1,2,...,a-1\}$ ，则上式变为：
$\tag{11.1.4}\frac{r^2}{m^2+mr}<k<\frac{r^2}{m^2+mr}$
其中 $r<b,m<a$ ，这说明，若存在 $a,b$ 使区间 $\left[\frac{b^2}{a^2+ab},\frac{b^2}{a^2+ab-1}\right)$ 内有整数，则必存在 $r<b,m<a$ ，使区间 $\left[\frac{r^2}{m^2+mr},\frac{r^2}{m^2+mr}\right)$ 有整数。这就构造了一个无穷递降，矛盾。所以假设不成立，命题成立。
$\blacksquare$

题11.2 证明： $\sqrt 2$ 是无理数。
证明假设 $\sqrt 2$ 是有理数，那么存在互素的正整数 $p,q$ ，满足 $\frac{p}q=\sqrt 2$ ，从而有 $\tag{11.2.1}\frac{p^2}{q^2}=2$
于是知 $1<p/q<2$ ，所以存在一个 $r$ ，使 $\tag{11.2.2}p=q+r$
$1\le r<q\\(q,r)=1,$
代入(11.2.1)，化整并整理得： $2r+r^2/q=q\\$
所以 $q|r^2$ ，因 $(q,r)=1$ ，故 $q|r$ 。这与 $1\le r<q$ 矛盾。假设不成立，命题成立。

评注11.3 题11.2是一个古老的问题，一般使用无穷递降法解决，(11.2.2)巧妙构造并利用带余除法，推导一个整除性矛盾，最终证明了命题。

【11】整数问题
题11.1 已知，求证：(1) 不是整数。(2) 区间中没有整数。证明 (1) 假设是正整数，则关于b的二次方程...
随机生成一个长度为 10 的整数类型的数组，例如 [2, 10,
问题随机生成一个长度为 10 的整数类型的数组，例如 [2, 10, 3, 4, 5, 11, 10, 11, ...
整数划分问题
什么是整数划分？将正整数n表示成一系列正整数的和。例如5的划分：5(1) 5;(2) 4+1;(3) 3+2 3...
整数划分问题
将一个整数划分为多个整数想加的形式，并计算划分方法。例：6的划分：6=5+16=4+26=4+1+16=3+36=...
整数划分问题
整数划分问题是算法中的一个经典命题之一，有关这个问题的讲述在讲解到递归时基本都将涉及。所谓整数划分，是指把一个正整...
递归--整数划分问题
前置文章：递归算法：www.jianshu.com/p/703069f3ba3f . 在说到递归算法的时候，逃...
64位整数问题
题目描述输入正整数n，统计它的正因子个数，n<= 10^(12),例如n=30时，输出应该为8。源码剖析这...
LeetCode 386. Lexicographical Nu
问题描述给定一个整数 n，以字母顺序返回 1-n 之间的数字。比如：n = 13，那么返回 [1,10,11,...
Python 14
import math v11 =1 #创建整数常量1，创...
1016部分A+B
问题描述：正整数 A 的“DA（为 1 位整数）部分”定义为由 A 中所有 DA组成的新整数 PA。例如：给定 ...