## The maximum difference between the number of elements in the two sets of equal length of consecutive numbers that divisible by some prime numbers

Suppose that $$p_1,…,p_k$$ are distinct prime numbers.

Let $$f(n,l)$$ be equal to the number of elements from set $$\{n+1,n+2,…,n+l\}$$ that are divisible by some $$p_1,…,p_k$$. Is it true that $$\sup_{n,m,l \in \mathbb{N}} |f(n,l)-f(m,l)| = O(k).$$

## Prime counting function estimate sieve of Eratosthenes-Legendre

I’m trying to arrive at estimate 1.17 (page 21) of Koukoulopoulos lecture notes [https://dms.umontreal.ca/~koukoulo/documents/notes/sievemethods.pdf]

$$\#\{n \leq x : p|n \Rightarrow p > \sqrt{x}\} = \frac{(2e^{- \gamma}+ o(1))x}{\log x} + O(4^{(1+o(1))\frac{\sqrt{x}}{\log x}})$$

We start with $$\#\{n \leq x: p|n \Rightarrow p > \sqrt{x}\} = \lfloor{x}\rfloor – \sum_{i=1}^{r}\lfloor{\frac{x}{p_{i}}\rfloor}\pm\dots$$ by an inclusion-exclusion argument.

We have the estimate that $$\lfloor{x}\rfloor = x + O(1).$$ Therefore we obtain $$\#\{n \leq x: p|n \Rightarrow p > \sqrt{x}\} = x \prod_{p \leq \sqrt{x}}\Big(1 – \frac{1}{p}\Big).$$

Using Merten’s theorem that for $$z \geq 2$$ we have $$\prod_{p \leq z}\Big(1 – \frac{1}{p}\Big) = \frac{e^{- \gamma}}{\log z}\Big(1 + O\Big(\frac{1}{\log z}\Big)\Big),$$ gives

$$\#\{n \leq x: p|n \Rightarrow p > \sqrt{x}\} = \frac{xe^{- \gamma}}{\log{\sqrt{x}}}\Big(1 + O\Big(\frac{1}{\log{\sqrt{x}}}\Big)\Big) = \frac{2xe^{-\gamma}}{\log x}\Big(1 + O\Big(\frac{2}{\log x}\Big)\Big).$$

I can rewrite the inclusion-exclusion argument in terms of the Mobius function as is done in equation 1.1.6 (page 20), but then I don’t see how we get the overall result.

It’s mostly the asymptotic notation that I’m stuck on as I’m not too familiar with it yet, particularly using “little oh” notation inside of “big oh” notation.

Thanks.

## Arranging numbers in a circle such that the sums of neighbors and sums of diametric opposites are prime

I need to create a circle with numbers from 1 to n , however it is necessary to respect some rules:

1. All numbers from 1 to n are used in the circle only once.
2. The sum of two consecutive numbers is a prime number
3. The sum of a number with what is diametrically opposite it is also a prime number

So I need to create an algorithm that receives an integer n and determines whether there is a circle of size n, if it exists.

For example:

Program response: 1 6 7 16 15 8 5 12 11 18 13 10 3 4 9 14 17 2

I managed to get the expected result, but I do not know if I made the faster way, or if there is something badly written.

import java.sql.Date; import java.text.SimpleDateFormat; import java.util.ArrayList; import java.util.Vector;  import javax.swing.JOptionPane;  public class QuintoDesafio {      private static int j;     private static int k;      private static Vector primes  = new Vector();      public static void main(String[] args)      {           long start = System.currentTimeMillis();            ArrayList list = new ArrayList();          primes.add( new Integer( 2 ) );         primes.add( new Integer( 3 ) );         primes.add( new Integer( 5 ) );         primes.add( new Integer( 7 ) );         primes.add( new Integer( 11 ) );         primes.add( new Integer( 13 ) );         primes.add( new Integer( 17 ) );         primes.add( new Integer( 19 ) );         primes.add( new Integer( 23 ) );         primes.add( new Integer( 31 ) );         primes.add( new Integer( 37 ) );         primes.add( new Integer( 41 ) );          String n = JOptionPane.showInputDialog( "Input n (even) ");         int ene = Integer.parseInt( n );          for ( int i=1; i <= ene; i++ ) {             list.add( new Integer(i) );         }         exchange(list, 0);          long end  = System.currentTimeMillis();            System.out.println(new SimpleDateFormat("ss.SSS").format(new Date(end - start)));       }      static void exchange(ArrayList arr, int k){         boolean passed = true;           for(int i = k; i < arr.size(); i++){             java.util.Collections.swap(arr, i, k);             exchange(arr, k+1);             java.util.Collections.swap(arr, k, i);         }         if (k == arr.size() -1){             int half = arr.size()/2;              for ( int j=0; j<arr.size(); j++ ) {                 int one = (int) arr.get(j);                 int two;                 if ( j+1 == arr.size() ) {                     two = (int) arr.get(0);                 } else {                     two = (int) arr.get(j+1);                 }                 Integer number_test = new Integer( one+two );                 if ( !primes.contains( number_test )) {                     passed = false;                 }             }              for ( int j=0; j<half; j++ ) {                 int one = (int) arr.get(j);                 int two = (int) arr.get(j+half);                 Integer number_test = new Integer( one+two );                 if ( !primes.contains( number_test )) {                     passed = false;                 }             }             if ( passed ) {                 System.out.println(java.util.Arrays.toString(arr.toArray()));             }         }     } } $$$$ 

## Every radical ideal in the ring of algebraic integers a finite intersection of prime ideals

Is every radical ideal in the ring of algebraic integers (i.e. the integral closure of $$\mathbb{Z}$$ considered as a subring of $$\mathbb{C}$$ via the unique homomorphism of unital rings $$\mathbb{Z}\rightarrow\mathbb{C}$$) a finite intersection of prime ideals?

## Prime Sieve and brute force

Got caught up with this mornings C++ question.
So I though I would have a go.

#include <iostream> #include <vector> #include <cmath>  bool isPrime(std::size_t num, std::vector<std::size_t> const& primes) {     std::size_t max = std::sqrt(num);     for(auto const& prime: primes)     {            if (prime > max) {             return true;         }            if (num % prime == 0)         {                return false;         }        }        return true; }  std::size_t sieve(std::size_t size, std::vector<std::size_t>& results) {     // primeCandidates holds 0/1 for each potential prime candidate.     // The index represents the potential prime (index * 2 + 1)     // This allows us to ignore all factors of 2     // max is one past the highest prime candidate we can test for and store in primeCandidates     std::size_t const           max = size * 2 + 1;     std::vector<std::size_t>    primeCandidates(size, 1);       // Add some default well know primes.     results.push_back(2);     results.push_back(3);      // We will use the technique of incrementing by 2 then 4 then 2 then 4     // This means skip all factors of 2 and 3 automatically.     std::size_t       inc = 2;     std::size_t loop = 5;     for(; loop < max; loop += inc, inc = 6 - inc) {         std::size_t index = loop/2;          // If we find a candidate that is valid then add it to results.         if (primeCandidates[index]) {             results.push_back(loop);              // Now strain out all factors of the prime we just found.             for(; index < primeCandidates.size(); index += loop) {                 primeCandidates[index] = 0;             }            }        }        return loop; }  int main() {     std::size_t constexpr   primeRequired   = 1001;     std::size_t constexpr   siveStartSize   = 1000;      std::vector<std::size_t>    result;     result.reserve(primeRequired);      // Use the Sieve of Eratosthenes to get a basic set of primes.     std::size_t next = sieve(siveStartSize, result);      // Want to re-use the 2/4/2/4 increment pattern     // So work out the correct start point and increment value.     std::size_t inc  = next % 6 == 5 ? 2 : 4;      // We now use brute force checking each number against all the primes     // that we have already found.     while(result.size() <= primeRequired) {         if (isPrime(next, result)) {             result.emplace_back(next);         }            next += inc;         inc  = 6 - inc;     }         // Print out the primes we have found     for(auto val: result) {         std::cout << val << " ";     }        std::cout << "\n"; } 

## A curious prime counting approximation or just data overfitting?

I am not sure, if this is a research problem. If not I will move this question to ME: Let $$\Omega(n) = \sum_{p|n} v_p(n)$$, which we might view as a random variable. Let $$E_n = \frac{1}{n} \sum_{k=1}^n\Omega(k)$$ be the expected value and $$V_n=\frac{1}{n} \sum_{k=1}^n(E_n-\Omega(k))^2$$ be the variance. Then $$\pi(n) \approx \frac{n\gamma(\frac{V_n}{E_n},1.4854177\cdot \frac{V_n}{E_n^2})}{\Gamma(\frac{V_n}{E_n})}$$ where $$\Gamma=$$ Gamma function, $$\gamma=$$ lower incomplete gamma function.

Background: I was trying to fit the gamma distribution to the random variable $$\Omega(k)$$ ,$$1 \le k \le n$$. The value $$1.4854177$$ is fitted to some data. My question is, if there is any heuristic why this approximation should be good, if at all, or if this is just an overfitting problem?

Below you can find some sage code which implements this:

def Omega(n):     return sum([valuation(n,p) for p in prime_divisors(n)])  means = [] variances = [] xxs = [] omegas = [Omega(k) for k in range(1,10^4)] for nn in range(10^4,10^4+3*10^3+1):     n = nn     omegas.append(Omega(n))     print "---"     m = mean(omegas[1:-1])     v = variance(omegas[1:-1])     shape,scale = m^2/v,v/m     xx = find_root(lambda xx : n*(lower_gamma(shape,xx*1/scale)/gamma(shape) ).N()-prime_pi(n),1,2)     xx = 1.4854177706344873     approxPrimePi2 = n*(lower_gamma(shape,xx*1/scale)/gamma(shape) ).N()     primepi = prime_pi(n)     print primepi, approxPrimePi2,shape.N(),scale.N(),xx     print "---"     print "err2 = %s" % (abs(primepi-approxPrimePi2)/primepi)     xxs.append(xx)     means.append(m.N())     variances.append(v.N()) 

## Project Euler #7 10001st prime in C++

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10 001st prime number?

How to optimize this code?

#include <iostream>  bool is_prime(int num) {     for (int i = 2; i <= num/2; ++i)     {         if (num % i == 0)         {             return false;         }     }     return true; }  int main() {     int count = 2;     for (int i = 5; ; i = i+2)     {         if (is_prime(i))         {             count++;         }         if (count == 10001)         {             std::cout << i;             return 0;         }     } } `

## Root of a polynomial and its reciprocal modulo a prime

Fix a large prime $$p$$ and let $$k \leq 10 \sqrt{p}$$. What are the $$z\in \mathbb{F}_p$$ that satisfy $$f(z) = f(1/z) = 0,$$ where $$f(z) = (2-z) \cdots (2k-z) + (-1)^{k+1} \cdot 3 \cdots (2k+1)?$$

## Prove that is prime ideal in Z[x] if f(x) is irreducible over Z

I know (x^2+1)is prime ideal of Z[x] without being maximal ideal. It can be easily proved as quotient ring isomorphic to integral domain Z[i]. My question is the generalization of this i. e. If (x^2+1) is replaced by arbitrary irreducible polynomial f(x) over Z. Can anyone suggest me an outline of this proof ? Thank u..

## Greatest prime factor of n and n+1

For a positive integer $$n$$ we denote its largest prime factor by $$\operatorname{gpf}(n)$$. Let’s call a pair of distinct primes $$(p,q)$$ $$\textbf{nice}$$ if there are no natural numbers $$n$$ such that $$\operatorname{gpf}(n)=p, \operatorname{gpf}(n+1)=q$$ or $$\operatorname{gpf}(n)=q, \operatorname{gpf}(n+1)=p$$. For example, $$(2,19)$$ is nice.

Are there nice pairs $$(p,q)$$ with $$p,q>100$$?