0
$\begingroup$

The basic question is : has this system been considered before, and how do I find it? References to the literature would be most welcome, but I am asking for reasonable search terms. I will try the OEIS soon.

We are going to generate for each prime $p$ some fractions which are $k= \pi(p)$ in number. The denominators will be primarily divided by 2, and otherwise I am not going to simplify them. So for $p=5$ the last fraction could be written as $2/5$, but I will keep it at $6/15$ and just write the numerators. First, some numerators for the first four primes with denominator in parentheses.

1 (1)

1 2 (3)

1 8 6 (15)

1 22 58 24 (105)

I am generating a distribution of sizes of sets of (what I temporarily call) remainders modulo the first $k$ primes, so the $j$th fraction in each row indicates the proportion of occurrences where I have $j$ distinct remainders. Given a row for the prime before $p$, the denominator is $p$ times the previous denominator, the first entry is 1, and the $j$th entry is ($j$ times the $j$th entry in the previous row) plus (($p+1-j$ times the $(j-1)$th entry in the previous row). The final entry in each row is a product of terms of the form $(p-k)$. So the 58 above says more than half (58/105) of the numbers $n$ have exactly two distinct classes of numbers of the form $q*Ceil(n/q)$ where I let $q$ run over the $k=4$ smallest primes. (This set of ceiling numbers can have from 1 up to $k$ many members, but I just care about the relative sizes of the sets and not their arrangement on the number line.)

I would actually like some bounds on the expected value of $j$ given this distribution. It feels like the expected value should be near $k(e-1)/e$ , but I am doing the calculations by hand and have not gotten far. In any case I want to know if this system is in the literature, or how to have a good chance of finding it if it is.

Gerhard "My Kingdom For Search Terms?" Paseman, 2018.04.13.

Improve this question
$\endgroup$
5
  • $\begingroup$ In other words, if $p_1<p_2<\cdots$ are the odd primes in order and $q_k = p_1p_2\cdots p_k$, you are defining a triangular array of integers $c_{jk}$ $(k\ge0,\, 0\le j\le k)$ such that $c_{jk}$ is the number of integers in the range $\{1,\dots,q_k\}$ whose greatest common divisor with $q_k$ has exactly $k-j$ prime factors. What quantity exactly do you want bounds for? $\endgroup$
    – Greg Martin
    Commented Apr 13, 2018 at 19:21
  • $\begingroup$ I don't think that is what I am measuring. I am dealing with something more complex, and the above is my way of coping with it. The real measure is number of memory items used by an algorithm which modified an array called cmp, and I am attempting to fine tune an analysis to estimate this usage restricted to a small interval. I will continue with the toy problem which is represented above. Gerhard "Can Share His Toys Sometimes" Paseman, 2018.04.13. $\endgroup$
    – Gerhard Paseman
    Commented Apr 13, 2018 at 20:22
  • $\begingroup$ Let us pick n, and determine the number of distinct positive integers j less than p such that n+j is q*Ceil(n/q) for some q at most p. So j =5 might be one of these numbers, but not because n+5 is a multiple of 3 (because we only look at multiples of 3 very close to n. The k,j th number measures the relative frequency of the occurrence (this set has j members, when only the first k primes are considered). Thus every n is close to a near multiple of 2, but only a third of n are close enough to and below a near multiple of 6. Gerhard "These Primes Don't Jump Far" Paseman, 2018.04.13. $\endgroup$
    – Gerhard Paseman
    Commented Apr 13, 2018 at 20:30
  • $\begingroup$ To do my estimate involving cmp, it seems reasonable to ask for the expected size of this set when given a not too small prime p. I imagine the expected size is not far from 2k/3, but I just started looking at this a couple of hours ago. (In the previous comment, q is assumed prime.) Gerhard "Really Hot Off The Presses" Paseman, 2018.04.13. $\endgroup$
    – Gerhard Paseman
    Commented Apr 13, 2018 at 20:38
  • $\begingroup$ Hmm. In talking about the toy problem, I talked about positive j. It turns out I also want j=0. Gerhard "Back To Your Original Programming" Paseman, 2018.04.13. $\endgroup$
    – Gerhard Paseman
    Commented Apr 13, 2018 at 21:06

1 Answer 1

Reset to default
2
$\begingroup$

The numbers you give match "Second-order Eulerian triangle" at OEIS.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ Thank you. Even though it is the wrong sequence, it may end up helping. (I think they continue with the "prime" 9, where as my next row starts 1 54 372 560 168 with the prime 11.). Gerhard "Maybe My Sequence Is Wrong?" Paseman, 2018.04.13. $\endgroup$
    – Gerhard Paseman
    Commented Apr 13, 2018 at 23:08

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .