Search

Let ω ( n ) denote the number of distinct prime factors of n and let τ k ( n ) denote the k-fold divisor function. Adapting a method of Granville and Soundararajan, we evaluate the centralized moments of ω ( n ) , weighted by τ k ( n ) , and deduce a weighted version of the Erdős-Kac Theorem.

In this paper, we study the Cartesian product of signed graphs as defined by Germina, Hameed and Zaslavsky (2011). Here we focus on its algebraic properties and look at the chromatic number of some Cartesian products. One of our main results is the unicity of the prime factor decomposition of signed graphs. This leads us to present an algorithm to compute this decomposition in linear time based on a decomposition algorithm for oriented graphs by Imrich and Peterin (2018). We also study the chromatic number of a signed graph, that is the minimum order of a signed graph to which the input signed graph admits a homomorphism, of graphs with underlying graph of the form P n □ P m , of Cartesian products of signed paths, of Cartesian products of signed complete graphs and of Cartesian products of signed cycles.

We study the normal number of prime factors of a f ( p ) + a g ( p ) with p prime and f , g distinct Hecke eigenforms of weight two. Assuming a quasi-generalized Riemann hypothesis, we show that the normal order is log log p . We also obtain an estimate for the number of primes p for which a f ( p ) + a g ( p ) = 0 .

Let p be a rational prime and q a power of p. Let n be a non-constant monic polynomial in F q [ t ] which has a prime factor of degree prime to q − 1 . In this paper, we define a Drinfeld modular curve Y 1 Δ ( n ) over A [ 1 / n ] and study the structure around cusps of its compactification X 1 Δ ( n ) , in a parallel way to Katz-Mazur's work on classical modular curves. Using them, we also define a Hodge bundle over X 1 Δ ( n ) such that Drinfeld modular forms of level Γ 1 ( n ) , weight k and some type are identified with global sections of its k-th tensor power.

Semi-prime factorization is an increasingly important number theoretic problem, since it is computationally intractable. Further, this property has been applied in public-key cryptography, such as the Rivest–Shamir–Adleman (RSA) encryption systems for secure digital communications. Hence, alternate approaches to solve the semi-prime factorization problem are proposed. Recently, Pythagorean tuples to factor semi-primes have been explored to consider Fermat’s Christmas theorem, with the two squares having opposite parity. This paper is motivated by the property that the integer separating these two squares being odd reduces the search for semi-prime factorization by half. In this paper, we prove that if a Pythagorean quadruple is known and one of its squares represents a Pythagorean triple, then the semi-prime is factorized. The problem of semi-prime factorization is reduced to the problem of finding only one such sum of three squares to factorize a semi-prime. We modify the Lebesgue identity as the sum of four squares to obtain four sums of three squares. These are then expressed as four Pythagorean quadruples. The Brahmagupta–Fibonacci identity reduces these four Pythagorean quadruples to two Pythagorean triples. The greatest common divisors of the sides contained therein are the factors of the semi-prime. We then prove that to factor a semi-prime, it is sufficient that only one of these Pythagorean quadruples be known. We provide the algorithm of our proposed semi-prime factorization method, highlighting its complexity and comparative advantage of the solution space with Fermat’s method. Our algorithm has the advantage when the factors of a semi-prime are congruent to 1 modulus 4. Illustrations of our method for real-world applications, such as factorization of the 768-bit number RSA-768, are established. Further, the computational viabilities, despite the mathematical constraints and the unexplored properties, are suggested as opportunities for future research.

Let N be a sufficiently large real number. In this paper, it is proved that, for $$1

In this paper, we give a new framework for constructing perfect sequences, called generalized Milewski sequences, over various alphabets including Polyphase (PSK) as well as Amplitude-and-Polyphase (APSK) in general, and for constructing optimal sets of such perfect sequences by using combinatorial designs, called circular Florentine arrays. Specifically, we prove that, given any positive integer $m\geq 1$ , (i) there exists a perfect sequence of period $mN^{2}$ for any positive integer $N$ if there exists a perfect sequence (polyphase or not) of length $m$ ; (ii) an optimal $k$ -set of perfect sequences of length $mN^{2}$ can be constructed if there exist both a $k \times N$ circular Florentine array and an optimal $k$ -set of perfect sequences all of length $m$ . This enables us to find some optimal $k$ -set of perfect sequences where $k > p_{\text {min}}-1$ , where $p_{\text {min}}$ is the smallest prime factor of $mN^{2}$ .

Let [Formula: see text] be a fixed positive number. Define [Formula: see text] as the number of positive integers [Formula: see text] having no prime factors [Formula: see text], and define [Formula: see text] as the number of positive integers [Formula: see text] having [Formula: see text] prime factors [Formula: see text], with all the other prime factors [Formula: see text]. In this paper, we give an asymptotic estimate for the ratio [Formula: see text], provided that [Formula: see text], [Formula: see text], and [Formula: see text] as [Formula: see text]. Also, combining this estimate with conventional ones for [Formula: see text], we provide sharp estimates for [Formula: see text].

A natural variant of Lehmer’s conjecture that the Ramanujan $$\tau $$ -function never vanishes asks whether, for any given integer $$\alpha $$ , there exist any $$n \in \mathbb {Z}^+$$ such that $$\tau (n) = \alpha $$ . A series of recent papers excludes many integers as possible values of the $$\tau $$ -function using the theory of primitive divisors of Lucas numbers, computations of integer points on curves, and congruences for $$\tau (n)$$ . We synthesize these results and methods to prove that if $$0< \left| \alpha \right| < 100$$ and $$\alpha \notin T := \{2^k, -24,-48, -70,-90, 92, -96\}$$ , then $$\tau (n) \ne \alpha $$ for all $$n > 1$$ . Moreover, if $$\alpha \in T$$ and $$\tau (n) = \alpha $$ , then n is square-free with prescribed prime factorization. Finally, we show that a strong form of the Atkin-Serre conjecture implies that $$\left| \tau (n) \right| > 100$$ for all $$n > 2$$ .

The purpose of this study was to describe students' communication in solving prime factors using written and oral communication. This study uses a qualitative and descriptive approach. The subjects of this study were 46 seventh grade students of Simanjaya Lamongan, East Java, Indonesia, Middle School who had obtained prime factor material. Data analysis was obtained by using a test of prime factors and interviews. Based on the results of data analysis, it was concluded that: 1) Written communication, as many as 40 students were able to communicate in writing with a percentage of 87% and 6 students were unable to communicate in writing with a percentage of 13%; 2) Oral communication, at this stage interviews were conducted by taking the subject as many as two students taken from one student who is able to communicate in writing and one student who is not able to communicate in writing, the results obtained that students are able to communicate in writing are also able to communicate verbally. verbally, while students who are not able to communicate in writing, it turns out that students are able to communicate orally. From the explanation above, it can be concluded that students are able to explain concepts into mathematical language, students are able to explain mathematical arithmetic operations, students are able to explain mathematical solutions and students are able to convey ideas or opinions. Thus, students can communicate in writing and orally well in solving prime factors.

Our initial problem is to represent classes $$m$$ modulo $$q$$ by a sum of three terms, two being taken from rather small sets $$\mathcal A$$ and $$\mathcal B$$ and the third one having an odd number of prime factors (the so-called irregular numbers in S. Ramanujan’s terminology) and lying in an interval $$[q^{20r},q^{20r}+q^{16r}]$$ for some given $$r\ge1$$ . We show that it is always possible to do so provided that $$|\mathcal A|\cdot|\mathcal B|\ge q(\log q)^2$$ . The proof leads us to study the trigonometric polynomials over irregular numbers in a short interval and to seek very sharp bounds for them. We prove in particular that $$\sum_{q^{20r}\le s \le q^{20r}+q^{16r}}e(sa/q)\ll q^{16r}(\log q)/\sqrt{\varphi(q)}$$ uniformly in $$r$$ , where $$s$$ ranges over the irregular numbers. We develop a technique initiated by Selberg and Motohashi to do so. In short, we express the characteristic function of the irregular numbers via a family of bilinear decompositions akin to Iwaniec’s amplification process, and that uses pseudo-characters or local models. The technique applies to the Liouville function, to the Mobius function and also to the von Mangoldt function, in which case it is slightly more difficult. It is however simple enough to warrant explicit estimates, and we prove, for instance, that $$\bigl|\sum_{X

Let G be a finite group, p be a prime divisor of |G|, and P be a Sylow p-subgroup of G. We prove that P is normal in a solvable group G if |G: ker φ|p′ = φ(1)p′ for every nonlinear irreducible monomial p-Brauer character φ of G, where ker φ is the kernel of φ and φ(1)p′ is the p′-part of φ(1).

Let N be a sufficiently large real number. In this paper, we prove that, for $$10$$ , the Diophantine inequality $$\begin{aligned} \big |p_1^c+p_2^c+p_3^c-N\big

We extend the Siegel-Walfisz theorem to a family of integer sequences that are characterized by constraints on the size of the prime factors. Besides prime powers, this family includes smooth numbers, almost primes and practical numbers., 11 pages

In this paper, we give an estimate of the lower bounds of the least common multiple of $$a,a+b,\ldots ,a+kb$$ for $$(a,b)=1,k\in \textit{N}^+$$ . Precisely, we prove that for any two coprime positive integers a and b, we have $$\begin{aligned} L_{a,b,k}\ge \prod \limits _{p\mid b}p^{\text {Ord}_{p}^{k!}}\frac{1}{k!}\prod \limits _{i=0}^{k}(a+ib), \end{aligned}$$ where $$L_{a,b,k}$$ is the least common multiple of $$a,a+b,\ldots ,a+kb$$ and $$\text {Ord}_p^{k!}$$ denotes the least s for which $$p^s\mid k!$$ but $$p^{s+1}\not \mid k!$$ . In addition, we obtain a corollary that there is a number containing a prime divisor greater than k in the set $$\{a,a+b,\ldots ,a+kb\}$$ for $$(a,b)=1,b\ge 2$$ .

Let G be a finite group. We prove that if every self-centralizing subgroup of G is nilpotent or subnormal or a TI-subgroup, then every subgroup of G is nilpotent or subnormal. Moreover, G has either a normal Sylow p-subgroup or a normal p-complement for each prime divisor p of |G|.

We establish an analog of the Hardy–Ramanujan inequality for counting members of sifted sets with a given number of distinct prime factors. In particular, we establish a bound for the number of shifted primes p + a below x with k distinct prime factors, uniformly for all positive integers k.

Let $$D_n(x;a)$$ and $$E_n(x;a)\in {\mathbb {F}}_q[x]$$ be Dickson polynomials of first and second kind respectively, where $${\mathbb {F}}_q$$ is a finite field with q elements. In this article we show explicitly the irreducible factors of these polynomials in the case that every prime divisor of n divides $$q-1$$ . This result generalizes the results found in (Finite Fields Appl. 3:84–96, 1997; Explicit factorization of cyclotomic and Dickson polynomials over finite fields, Springer, Berlin, 2007; Finite Fields Appl. 38:40-56, 2016; Discrete Math. 342:111618, 2019).

Denote by P + ( n ) the largest prime factor of an integer n. In this paper, we show that the Elliott-Halberstam conjecture for friable integers (or smooth integers) implies three conjectures concerning the largest prime factors of consecutive integers, formulated by Erdős-Turan in the 1930s, by Erdős-Pomerance in 1978, and by Erdős in 1979 respectively. More precisely, assuming the Elliott-Halberstam conjecture for friable integers, we deduce that the three sets E 1 = { n ⩽ x : P + ( n ) ⩽ x s , P + ( n + 1 ) ⩽ x t } , E 2 = { n ⩽ x : P + ( n ) P + ( n + 1 ) x α } , E 3 = { n ⩽ x : P + ( n ) P + ( n + 1 ) } have an asymptotic density ρ ( 1 / s ) ρ ( 1 / t ) , ∫ T α u ( y ) u ( z ) d y d z , 1/2 respectively for s , t ∈ ( 0 , 1 ) , where ρ ( ⋅ ) is the Dickman function, and T α , u ( ⋅ ) are defined in Theorem 2.

The Piatetski-Shapiro sequences are sequences of the form $ (\left\lfloor {{n^c}} \right\rfloor)_{n = 1}^\infty $ for $ c > 1 $ and $ c \not\in \mathbb{N} $. It is conjectured that there are infinitely many primes in Piatetski-Shapiro sequences for $ c \in (1, 2) $. For every $ R \ge 1 $, we say that a natural number is an $ R $-almost prime if it has at most $ R $ prime factors, counted with multiplicity. In this paper, we prove that there are infinitely many $ R $-almost primes in Piatetski-Shapiro sequences if $ c \in (1, c_R) $ and $ c_R $ is an explicit constant depending on $ R $.

After briefly describing the origin and the scope of the Turan–Kubilius inequality, we show how this important inequality leads to the law of large numbers for the prime factors belonging to the middle region of a random natural number. Finally, we show how the same idea is implemented for a sparser subset, the set of shifted primes.

Optimization algorithms play a central role in chemistry since optimization is the computational keystone of most molecular and electronic structure calculations. Herein, we introduce the iterative power algorithm (IPA) for global optimization and a formal proof of convergence for both discrete and continuous global search problems, which is essential for applications in chemistry such as molecular geometry optimization. IPA implements the power iteration method in quantics tensor train (QTT) representations. Analogous to the imaginary time propagation method with infinite mass, IPA starts with an initial probability distribution ρ0(x) and iteratively applies the recurrence relation ρk+1(x) = U(x) ρk(x)/∥Uρk∥L1, where U(x) = e-V(x) is defined in terms of the potential energy surface (PES) V(x) with global minimum at x = x*. Upon convergence, the probability distribution becomes a delta function δ(x - x*), so the global minimum can be obtained as the position expectation value x* = Tr[x δ(x - x*)]. QTT representations of V(x) and ρ(x) are generated by fast adaptive interpolation of multidimensional arrays to bypass the curse of dimensionality and the need to evaluate V(x) for all possible values of x. We illustrate the capabilities of IPA for global search optimization of two multidimensional PESs, including a differentiable model PES of a DNA chain with D = 50 adenine-thymine base pairs, and a discrete non-differentiable potential energy surface, V(p) = mod(N,p), that resolves the prime factors of an integer N, with p in the space of prime numbers {2, 3,..., pmax} folded as a d-dimensional 21 × 22 × ··· × 2d tensor. We find that IPA resolves multiple degenerate global minima even when separated by large energy barriers in the highly rugged landscape of the potentials. Therefore, IPA should be of great interest for a wide range of other optimization problems ubiquitous in molecular and electronic structure calculations.

We examine two counting problems that seem very group-theoretic on the surface but, on closer examination, turn out to concern integers with restrictions on their prime factors. First, given an odd prime $q$ and a finite abelian $q$-group $H$, we consider the set of integers $n\le x$ such that the Sylow $q$-subgroup of the multiplicative group $(\mathbb Z/n\mathbb Z)^\times$ is isomorphic to $H$. We show that the counting function of this set of integers is asymptotic to $K x(\log\log x)^\ell/(\log x)^{1/(q-1)}$ for explicit constants $K$ and $\ell$ depending on $q$ and $H$. Second, we consider the set of integers $n\le x$ such that the multiplicative group $(\mathbb Z/n\mathbb Z)^\times$ is "maximally non-cyclic", that is, such that all of its prime-power subgroups are elementary groups. We show that the counting function of this set of integers is asymptotic to $A x/(\log x)^{1-\xi}$ for an explicit constant $A$, where $\xi$ is Artin's constant. As it turns out, both of these group-theoretic problems can be reduced to problems of counting integers with restrictions on their prime factors, allowing them to be addressed by classical techniques of analytic number theory., Comment: 21 pages

Algorithms for interpolating a polynomial f from its evaluation points whose running time depends on the sparsity to f the polynomial when it is represented as a linear combination of t Chebyshev Polynomials of the First Kind with non-zero scalar coefficients are given by Lakshman and Saunders (1995), Kaltofen and Lee (2003) and Arnold and Kaltofen (2015). The term degrees are computed from values of Chebyshev Polynomials of those degrees. We give an algorithm that computes those degrees in the manner of the Pohlig and Hellman algorithm (1978) for computing discrete logarithms modulo a prime number p when the factorization of p - 1(or p + 1) has small prime factors, that is, when p - 1(or p + 1) is smooth. Our algorithm can determine the Chebyshev degrees modulo such primes in bit complexity log(p)(O(1)) times the squareroot of the largest prime factor of p - 1( or p + 1). (C) 2020 Elsevier Ltd. All rights reserved. National Science FoundationNational Science Foundation (NSF) [CCF-1421128, CCF-1708884] Supported by National Science Foundation CCF-1421128 and CCF-1708884.

Let $$\mathcal {P}_r$$ denote an almost-prime with at most r prime factors, counted according to multiplicity. In this paper, we establish a theorem of Bombieri–Vinogradov type for the Piatetski–Shapiro primes $$p=[n^{1/\gamma }]$$ with $$\frac{85}{86}

In Sarkozy (2001) the third author of this paper presented two conjectures on the additive decomposability of the sequence of ”smooth” (or ”friable”) numbers. Elsholtz and Harper (2015) proved (by using sieve methods) the second (less demanding) conjecture. The goal of this paper is to extend and sharpen their result in three directions by using a different approach (based on the theory of S -unit equations).