It has been conjectured that the sequence @math modulo @math is uniformly distributed. The distribution of this sequence is signifcant in relation to unsolved problems in number theory including the Collatz conjecture. In this paper, we describe an algorithm to compute @math modulo @math to @math . We then statistically analyze its distribution. Our results strongly agree with the hypothesis that @math modulo 1 is uniformly distributed.
To our knowledge no research has been published to evaluate numerically the distribution of the sequence @math modulo 1. However, the distribution of this sequence has been studied in relation to another topic: Mahler's Z-numbers. A Z-number is a real number @math such that @math for all @math . Mahler conjectured in 1968 that no Z-numbers exist @cite_10 .
@cite_10
2000931246 2952993179 2964092005 2064379477
Let f be a random Boolean formula that is an instance of 3-SAT. We consider the problem of computing the least real number k such that if the ratio of the number of clauses over the number of variables of f strictly exceeds k , then f is almost certainly unsatisfiable. By a well-known and more or less straightforward argument, it can be shown that kF5.191. This upper bound was improved by to 4.758 by first providing new improved bounds for the occupancy problem. There is strong experimental evidence that the value of k is around 4.2. In this work, we define, in terms of the random formula f, a decreasing sequence of random variables such that, if the expected value of any one of them converges to zero, then f is almost certainly unsatisfiable. By letting the expected value of the first term of the sequence converge to zero, we obtain, by simple and elementary computations, an upper bound for k equal to 4.667. From the expected value of the second term of the sequence, we get the value 4.601q . In general, by letting the U This work was performed while the first author was visiting the School of Computer Science, Carleton Ž University, and was partially supported by NSERC Natural Sciences and Engineering Research Council . of Canada , and by a grant from the University of Patras for sabbatical leaves. The second and third Ž authors were supported in part by grants from NSERC Natural Sciences and Engineering Research . Council of Canada . During the last stages of this research, the first and last authors were also partially Ž . supported by EU ESPRIT Long-Term Research Project ALCOM-IT Project No. 20244 . †An extended abstract of this paper was published in the Proceedings of the Fourth Annual European Ž Symposium on Algorithms, ESA’96, September 25]27, 1996, Barcelona, Spain Springer-Verlag, LNCS, . pp. 27]38 . That extended abstract was coauthored by the first three authors of the present paper. Correspondence to: L. M. Kirousis Q 1998 John Wiley & Sons, Inc. CCC 1042-9832r98r030253-17 253 A @math -modal probability distribution over the discrete domain @math is one whose histogram has at most @math "peaks" and "valleys." Such distributions are natural generalizations of monotone ( @math ) and unimodal ( @math ) probability distributions, which have been intensively studied in probability theory and statistics. In this paper we consider the problem of (i.e., performing density estimation of) an unknown @math -modal distribution with respect to the @math distance. The learning algorithm is given access to independent samples drawn from an unknown @math -modal distribution @math , and it must output a hypothesis distribution @math such that with high probability the total variation distance between @math and @math is at most @math Our main goal is to obtain algorithms for this problem that use (close to) an information-theoretically optimal number of samples. We give an efficient algorithm for this problem that runs in time @math . For @math , the number of samples used by our algorithm is very close (within an @math factor) to being information-theoretically optimal. Prior to this work computationally efficient algorithms were known only for the cases @math Birge:87b,Birge:97 . A novel feature of our approach is that our learning algorithm crucially uses a new algorithm for as a key subroutine. The learning algorithm uses the property tester to efficiently decompose the @math -modal distribution into @math (near-)monotone distributions, which are easier to learn. In 1930s Paul Erdős conjectured that for any positive integer C in any infinite ±1 sequence (x n ) there exists a subsequence x d , x 2d , x 3d ,…, x kd , for some positive integers k and d, such that ( i=1 ^k x_ id >C ). The conjecture has been referred to as one of the major open problems in combinatorial number theory and discrepancy theory. For the particular case of C = 1 a human proof of the conjecture exists; for C = 2 a bespoke computer program had generated sequences of length 1124 of discrepancy 2, but the status of the conjecture remained open even for such a small bound. We show that by encoding the problem into Boolean satisfiability and applying the state of the art SAT solver, one can obtain a discrepancy 2 sequence of length 1160 and a proof of the Erdős discrepancy conjecture for C = 2, claiming that no discrepancy 2 sequence of length 1161, or more, exists. We also present our partial results for the case of C = 3. The frequency moments of a sequence containing mi elements of type i, for 1 i n, are the numbers Fk = P n=1 m k . We consider the space complexity of randomized algorithms that approximate the numbers Fk, when the elements of the sequence are given one by one and cannot be stored. Surprisingly, it turns out that the numbers F0;F1 and F2 can be approximated in logarithmic space, whereas the approximation of Fk for k 6 requires n (1) space. Applications to data bases are mentioned as well.