10
\$\begingroup\$

Follow-up of my previous challenge, inspired by @emanresu A's question, and proven possible by @att (Mathematica solution linked)

For the purposes of this challenge, a 1-2-3-5-7... sequence is an infinite sequence of increasing positive integers such that for any positive integer \$n,\$ exactly one of the set of numbers \$n, 2n, 3n, 5n, 7n, \dotsc\$ appears in the sequence, with the set continuing for every product of \$n\$ and a prime number. For example, no such sequence can contain 18 and 42, since they are both multiples of 6 by a prime number. There exist multiple such sequences, so any one will suffice.

Your challenge is to output any 1-2-3-5-7... sequence. Standard rules apply - you may output as a function that takes \$n\$ and outputs the \$n\$th term or first \$n\$ terms, or output an infinite sequence in some form. You may use 0- or 1-indexing.

This is , so shortest wins!

Some additional math problems for anyone interested (I don't know the answers this time):

  1. What is the cardinality of the set of 1-2-3-5-7... sequences?
  2. Find the natural density of any or all 1-2-3-5-7... sequences in the natural numbers.
\$\endgroup\$
7
  • 3
    \$\begingroup\$ I can’t parse “ exactly one of n and all the multiples of n by the primes appears in the sequence”. Can you explain more? \$\endgroup\$
    – Simd
    Apr 15 at 8:14
  • \$\begingroup\$ So you'd prefer "exactly one of all the multiples of n by one and the primes appears"? \$\endgroup\$
    – Neil
    Apr 15 at 10:50
  • 2
    \$\begingroup\$ "a 1-2-3-5-7... sequence is an infinite sequence of increasing positive integers such that the sequence contains exactly one integer from any set \$S\$<sub>\$i\$</sub> that contains an integer \$i\$ and the integers \$Pi\$ where \$P\$ is the set of prime numbers. \$S\$<sub>1</sub> \$= (1, 2, 3, 5, 7, 11...)\$, and the sequence may only contain one of the integers in that set. \$S\$<sub>2</sub> \$= (2, 4, 6, 10, 14, 22...)\$, and the sequence may only contain one of the integers in that set." ...? \$\endgroup\$ Apr 15 at 12:56
  • 1
    \$\begingroup\$ Perhaps it would be useful for the original poster to provide some examples and non-examples of 1-2-3-5-7 sequences \$\endgroup\$
    – Kopper
    Apr 15 at 14:15
  • \$\begingroup\$ Sorry, I believe it may have been more readable before, but someone suggested this change. I'll make it much more clear. An example is linked in the problem. \$\endgroup\$
    – Tbw
    Apr 15 at 16:17

4 Answers 4

5
\$\begingroup\$

JavaScript (V8), 82 bytes

for(i=0,g=x=>x%k?k<i&&g(x,g[-i%k++||i]=z+=!g[k]):z^g(x/k);k=2;z=1)g(++i)||print(i)

Try it online!

att's method but on \$\mathbb F_2^\infty\$ rather than \$\mathbb Z\$


cardinality: Map Z to P, still 2N

\$\endgroup\$
5
\$\begingroup\$

05AB1E, 11 9 bytes

∞ʒÓ2ôÆƶO_

Try it online! Outputs the infinite sequence (well on TIO it will time out after about 18000). Explanation: Port of @att's formula (numbers where the dot product of the prime factorisation exponents with the sequence of nonzero integers in order of absolute value is zero). Edit: Saved 2 bytes thanks to @KevinCruijssen.

∞           Infinite sequence of positive integers
 ʒ          Filtered where
  Ó         Exponents of prime factorisation
   2ô       Split into pairs
     Æ      Reduced by subtraction
      ƶ     Multiply each value by its index (1-indexed)
       O_   Has zero sum
\$\endgroup\$
6
  • \$\begingroup\$ Interestingly ∞ε>2‰`·<*} is four times faster than ∞D(.ι. \$\endgroup\$
    – Neil
    Apr 14 at 8:46
  • \$\begingroup\$ ∞D(.ι* can be 2ôƶÆ for -2 bytes (and it's also faster, it now times out at ~18000): try it online. \$\endgroup\$ Apr 15 at 7:18
  • \$\begingroup\$ @KevinCruijssen Thanks, that helped me find üÆ. \$\endgroup\$
    – Neil
    Apr 15 at 7:32
  • \$\begingroup\$ Are you sure that's correct? üÆƶ does give a different output (1,2,4,6,8,16,20,30,32,36,... than 2ôƶÆ (1,6,28,35,36,45,104,130,143,168,...). \$\endgroup\$ Apr 15 at 8:06
  • 1
    \$\begingroup\$ ü is indeed for all overlapping pairs. E.g. for [a,b,c,d,e], 2ôÆ would be [a-b,c-d,e], whereas üÆ/ü- would be [a-b,b-c,c-d,d-e]. \$\endgroup\$ Apr 15 at 8:47
1
\$\begingroup\$

Wolfram Language (Mathematica), 74 bytes

f@n_:=f/;!Or@@CompositeQ/@NumeratorDenominator[i/n]=Print@n
f@i~Do~{i,∞}

Try it online!

Greedy algorithm. Outputs (certain products of distinct primes)*(all squares) indefinitely. Appears to be equivalent to l4m2's solution.

\$\endgroup\$
2
  • 2
    \$\begingroup\$ These are probably products of distinct primes whose indices (in 2,3,5,7,... 1-indexed) bitwise-xor to 0. \$\endgroup\$
    – xnor
    Apr 16 at 2:04
  • \$\begingroup\$ @xnor that is certainly the way l4m2's works, and it seems to be the exact same sequence. \$\endgroup\$
    – Tbw
    Apr 16 at 3:13
1
\$\begingroup\$

Python 3 (sympy), 126 bytes

from sympy import*
s=[]
g=x=0
while 1:
 x+=1;g=nextprime(g)
 if all(f%x or~-isprime(f//x)*(x-f)for f in s):print(g*x);s+=[g*x]

Try it online!

Not the shortest, not the fastest, but it does (partially) answer the additional math problems.

First we'll make some definitions to facilitate the proof of why this algorithm works. For any \$i \in \mathbb{N}\$ let \$S_i\$ be the sequence \$i,2i,3i,5i,\dots\$ that is, all numbers which are a product of \$i\$ and a prime or 1. We are looking to generate a sequence \$A\$ such that for all \$i \in \mathbb{N}\$ we have that \$|A \cap S_i|=1\$.

We construct our desired sequence as follows. We begin with an empty sequence, we then count up through all \$i \in \mathbb{N}\$, and at each step if we already have an element from \$S_i\$ in the sequence we do nothing, if we don't then we add \$i \cdot p_i\$ to the sequence, where \$p_i\$ is the \$i^{th}\$ prime number. It should be clear why this method will construct a sequence with at least one element from each \$S_i\$, but we also need to show that it does not have more than one element from any \$S_i\$. To show this we demonstrate the following two properties of \$i \cdot p_i\$.

First, \$i \cdot p_i \not \in S_j\$ for all \$j<i\$. This must be the case since if \$i \cdot p_i \in S_j\$ for some \$j<i\$ that would imply that \$i \cdot p_i= q \cdot a \cdot p_i\$ where \$q\$ is prime (or 1) and \$a \cdot p_i = j\$ but this is a contradiction since \$p_i > i > j\$

Second there can exist no \$j,k\$ where \$j<i<k\$ such that \$i \cdot p_i \in S_k\$ and \$j \cdot p_j \in S_k\$. This must also be true, since if there exist some \$j,k\$ where \$j<i<k\$ such that \$i \cdot p_i \in S_k\$ and \$j \cdot p_j \in S_k\$ that would imply that \$i \cdot p_i= q \cdot a \cdot p_i\$ where \$q\$ is prime (or 1) and \$a \cdot p_i = k\$ and that \$j \cdot p_j= r \cdot b \cdot p_j\$ where \$r\$ is prime (or 1) and \$b \cdot p_j = k\$. This would mean that \$a \cdot p_i = b \cdot p_j\$, and further that \$p_i\$ is a factor of \$b \cdot p_j\$, but this cannot be the case, since \$p_i > p_j\$ and \$p_i > i>j \geq b\$.

With these two properties we have shown that our sequence will never have more than one element from any \$S_i\$ since that would require adding an element to the sequence which is in a common \$S_i\$ with an element already in the sequence, which would require one of the above properties to be false.

So what about the answers to the additional math problems? Well if we look back through the proof we'll note that there's nothing particularly special about adding \$i \cdot p_i \$. In fact we should be able to choose any prime in place of \$p_i\$ so long as it is greater than \$i\$ and greater than the last prime we chose. This means that since there are infinite primes, we have infinite choices for what number to add each time we add a number to the sequence. Specifically, we make a countably infinite number of choices each with a countably infinite number of valid options, meaning we can construct an uncountably infinite number of valid sequences in this way. Note that this method is not exhaustive, and there are valid sequences which cannot be constructed in this way as well.

As for the second question, since the natural density of the primes is 0, any valid sequence constructed using the method described here will also have a natural density of 0 since the sequence will be more sparse than the primes by the nature of the construction.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.