number theory - Minimal positive integer n which is divisible by d and has sum of digits equal to s

I found this problem on codeforces ( and I'm trying to understand a pretty elegant solution that was posted:#include<bits/stdc++.h>using namespace std;typedef long long ll;int d,s;struct node{ int mod,sum; char s[700]; int len;};queue<node> Q;bool v[512][5200];int main(){ scanf("%d%d",&d,&s); Q.push({0,0,0,0}); while(!Q.empty()) { node a=Q.front();Q.pop(); for(int i=0;i<10;i++) { node b=a; b.s[b.len++]=i+'0'; ...Read more

error correction - Code that maps numbers from one number to another with where each number has a distance greater than 1

I need to tag a load of books with a unique id. Because human error would really mess with the system i need the code to detect if one of the numbers is wrong. That means that no two elements of the code can have a hamming distance of 1. Or have a parity check method or something again such that some errors can be detected. I would normally post what I've done so far, but I don't know where to start really.Thanks...Read more

number theory - Calculating sum of geometric series (mod m)

I have a series S = i^(m) + i^(2m) + ............... + i^(km) (mod m) 0 <= i < m, k may be very large (up to 100,000,000), m <= 300000I want to find the sum. I cannot apply the Geometric Progression (GP) formula because then result will have denominator and then I will have to find modular inverse which may not exist (if the denominator and m are not coprime).So I made an alternate algorithm making an assumption that these powers will make a cycle of length much smaller than k (because it is a modular equation and so I would obtai...Read more

Number Theory Congruence Modulo

I’m self-studying number theory using George Andrew’s textbook.I’m at the chapter of congruence modulo. There is one or two parts that I couldn’t quite figure out. Wonder if someone could point things out for me.By definition, if c≠0, a≡b(mod c) provided that (a-b)/c is an integer. That is c|(a-b).If a= 5, b=-3, c=85 is congruent to -3 modulo 8, 5≡-3(mod 8) since (5-(-3))/8 is an integer of 1.I read else where that congruence modulo could also be interpreted as the remainder of (a/c) is equal to the remainder of (b/c).If that’s the case, using ...Read more

How to find total number of divisors upto N?

Given a number N, have to find number the divisors for all i where i>=1 and i<=N. Can't figure it out.Do I have to this using prime factorization? Limit is N<=10^9Sample Output:1 --> 12 --> 33 --> 54 --> 85 --> 106 --> 147 --> 168 --> 209 --> 2310 --> 2711 --> 2912 --> 3513 --> 3714 --> 4115 --> 45...Read more

number theory - Let $p$ be prime and $0<a< p$ an integer such that $ \Big({a\over p}\Big) =1$ Then there exists integers $x,y$ such that $p=x^2-ay^2$.

Let $p$ be prime and $0<a< p$ an integer such that $$ \Big({a\over p}\Big) =1$$Then there exists integers $x,y$ such that $p=x^2-ay^2$.Edit: For which primes is this true? From CalebKoch answer we see this is not true in general. Can you sugest me a literature where I can find a theory of this.I suspect, if it is true, then it has something to do with a Thue theorem. found this interesting results: more

number theory - Bound for divisor function

I have been searching for a bound of the divisor function $d(n)$, meaning the number of divisors of n. So far I have found that it can be bounded by $$ d(n) \le e^{O(\frac{\log n}{\log \log n})}$$Wigert has proven the constant is $\log 2$ so $$ d(n) \le e^{(\log 2+ o(1)) \frac{\log n}{\log \log n}} $$However, when I tried to check that bound on a computer, it did not seem right. I have drawn $d(n)$ (in blue), $e^{\frac{\log n}{\log \log n}}$ (in red) and $e^{\log 2 \frac{\log n}{\log \log n}}$ (in green) on the following graph: Furthermore, wh...Read more

number theory - Can one show a beginning student how to use the $p$-adics to solve a problem?

I recently had a discussion about how to teach $p$-adic numbers to high school students. One person mentioned that they found it difficult to get used to $p$-adics because no one told them why the $p$-adics are useful.As a graduate student in algebraic number theory, this question is easy to answer. But I'm wondering if there's a way to answer this question to someone who only knows very basic things about number theory and the $p$-adics. I'm thinking of someone who has learned over the course of a few days what the $p$-adic numbers are, what t...Read more

number theory - Calculating the median in the St. Petersburg paradox

I am studying a recreational probability problem (which from the comments here I discovered it has a name and long history). One way to address the paradox created by the problem is to study the median value instead of the expected value. I want to calculate the median value exactly (not only find bounds or asymptotic values). I have found a certain approach and I am stuck in a specific step. I present my analysis and I would like some help on that specific step. [Note: Other solutions to the general problem are welcome (however after the revel...Read more

number theory - IMO 1997 problem 6

For each positive integer $n$ , let $f (n)$ denote the number of ways of representing $n$ as a sum of powers of $2$ with non-negative integer exponents. Representations which differ only in the ordering of their summands are considered to be the same. Prove that, for any integer $n \geqslant 3$, $$2^{n^2/4} < f (2^n) < 2^{n^2/2}.$$...Read more

The set of rational numbers of the form p/p', where p and p' are prime, is dense in $[0, \infty)$

I have been working through the exercises in Tenenbaum's "Introduction to analytic and probabilistic number theory" book, and I am stumped here (Exercise I.1.6). This is not a homework assignment, but just rather for my own edification. I know Tenenbaum's exercises are usually considered quite hard, so I don't feel as embarrassed to ask this question!For those not aware (I suspect most experts know this exercise and book inside and out), the homework problem reads as follows:Set $d_n = p_{n+1} - p_n$.Show that $p_n \sim n \log n \qquad (n \to...Read more

number theory - Is partition function increasing function?

I have some exercises which require knowing the number of partitions of particular numbers, so I used some python code which I found on internet to compute the values of the partition function for the values I want.But I noticed that $p(10)=p(12)=57$ and $p(11)=51$ where $p$ is the partition function - this what the program gave me! Before that, I guessed that the partition function is increasing, but the calculations by the code showed that it's not.So, is my guess right and the code has an error, or is my guess wrong?...Read more

Exponential generating function for the Bell numbers

I've recently come across the Bell numbers, defined as:\begin{equation*}B_{n} = \sum_{k=0}^{n}\binom{n}{k}B_{k}.\end{equation*}The exponential generating function of the Bell numbers is known to be:\begin{equation*}B(x) = e^{e^{x}-1}.\end{equation*}If I understand this correctly, the x-th Bell number can calso be computed using this generating function, yet when, for example, inserting the value 2 as input, the output is of course not 2; yet $B_{2} = 2$. What exactly does this function imply then---how is this related to Bell numbers?I realize ...Read more