16
\$\begingroup\$

If we have a finite list of elements we can determine the probability of any one element being drawn at random as the number of times it occurs divided by the total number of elements in the list.

For example if the list is [2,3,2,4] the probability of drawing 2 is \$\frac 1 2\$ since there are \$2\$ 2s and \$4\$ elements total.

For an infinite sequence we can't use this method. Instead what we can do is look at every prefix of the sequence determine the probability using the above method and then see if the limit of the probabilities converges. This looks like

$$ P(x, s_i) = \displaystyle\lim_{n\rightarrow\infty} \dfrac{\left|\left\{s_m\mid m<n,s_m=x\right\}\right|}{n} $$

For example if we have the sequence which alternates between 0 and 1, [0,1,0,1,0,1..., then the probability of drawing a 0 is \$\frac 1 2\$.

Now this is neat but sometimes the limit just doesn't converge, and so the probability of an element being drawn is undefined.

Your task will be to implement a sequence where for every positive integer its probability is undefined. This means that no matter what you pick this limit must not converge. It also means just as a side effect that every positive integer must appear an infinite number of times. Otherwise the probability would converge to \$0\$.

You may implement any sequence you wish as long as it fulfills the above. Your sequence should output non-negative integers. Zero is permitted to appear in the sequence but is not required to.

This challenge uses the defaults for sequence IO which can be found here.

This is so the goal is to minimize your source code with answers being scored in bytes.

\$\endgroup\$
9
  • \$\begingroup\$ When printing, what can we use as a separator? A single character, some amount of whitespace or any string of non-numerical characters? Also are leading zeros like "003" allowed? \$\endgroup\$
    – AnttiP
    Jan 26 at 10:32
  • \$\begingroup\$ @AnttiP IO is the default for sequences. If there is any ambiguity there it's better to take it up on meta than here. \$\endgroup\$
    – Wheat Wizard
    Jan 26 at 10:37
  • 4
    \$\begingroup\$ Related: Infinitely many ℕ, to output a sequence with each natural number infinitely many times. \$\endgroup\$
    – xnor
    Jan 26 at 10:37
  • \$\begingroup\$ It it OK if our sequence contains zeroes or negative values? \$\endgroup\$
    – xnor
    Jan 26 at 10:41
  • \$\begingroup\$ @xnor I will say that zero is fine and has no requirements (prob can be defined or undefined). But negative numbers should not appear in the sequence. \$\endgroup\$
    – Wheat Wizard
    Jan 26 at 10:44

4 Answers 4

8
\$\begingroup\$

Python 2, 24 bytes

lambda n:`n`.find("1")+1

Attempt This Online!

This is heavily based on @xnor's idea in the comments. It returns the (1-based) index of the most significant decimal "1" and 0 if there is none.

Why does it work?

for any cutoff 10^k the fraction of numbers below it that have the first "1" at position n (n<k) is asymptotically the same, in particular, it is bounded below by a positive number. But between 10^k and 2x10^k there are no such numbers, meaning that frequency will eventually fall to half its value (and then rise again) which is incompatible with convergence.

The case k=1 must be dealt with separately (easy) and k=0 is exempt by OP.

Python, 36 bytes

lambda n:int(bin(len(bin(n)))[3:],2)

Attempt This Online!

Takes an index and returns the corresponding value. Numbers are first mapped to the length of their binary representation. That way whatever this finally maps to is elevated to a probability of roughly 0.5. As a simple way to make sure every number comes back eventually, we take again the binary representation and use the most significant bit for modulo. In other words we remove it and all leading zeros that may be exposed.

The test code first shows the first 1000 items and then the unique values of the first 1000 blocks.

\$\endgroup\$
7
\$\begingroup\$

x86 32-bit machine code, 7 bytes

0F BD C1 0F BC C0 C3

Try it online!

Following the fastcall calling convention, this takes the 1-indexed n in ECX and returns the nth value in EAX.

In assembly:

.global f
f:
    bsr eax, ecx
    bsf eax, eax
    ret

This produces blocks of size 1, 2, 4, 8, 16, ... of the same number, so that each block raises its number's proportion to more than half. bsr (find highest position of a 1 bit) is used to obtain the 0-indexed block number.

The values used for the blocks are (0), 0, 1, 0, 2, 0, 1, 0, 3, ...; these values are produced by bsf (find lowest position of a 1 bit) on the block number. (The result of bsf is officially undefined for a value of 0, but on at least some systems it consistently leaves the destination register unchanged, producing 0 for block 0.)

\$\endgroup\$
3
  • \$\begingroup\$ Can you clarify what the values of the blocks are? (I don't get the rule from the initial numbers you provide). It's not clear, for example, that each number appears infinitely many times \$\endgroup\$
    – Luis Mendo
    Jan 26 at 11:47
  • 2
    \$\begingroup\$ @LuisMendo The 0th block has value 0; for m>0, the mth block's value is the highest x such that 2^x divides m. \$\endgroup\$
    – m90
    Jan 26 at 11:49
  • \$\begingroup\$ It's not often that assembly is shorter than many high-level languages, and it always puts a smile on my face; thanks, sir! \$\endgroup\$ Jan 27 at 14:10
3
\$\begingroup\$

Python 3, 41 bytes

j=1
while j:j+=1;print([str(j)[1:]]*2**j)

Try it online!

Here, we increment j and strip the leading digit, to get a sequence where every number appears infinitely often. Let's call the stripped number k. Then we output 2**j copies of k. This has the property that the probability of k jumps up to 50%, when we ouput k, then decreseas by half after every iteration. This means that the probability of k doesn't converge.

The probability jumps occur because \$2^j>\displaystyle\sum_{n=1}^{j-1}2^n\$

The IO format is a bit rough, to say the least. The output is a non-digit separated list of numbers, which may have leading zeros.

Python 3, 48 bytes

j=10
while j:j+=1;print(*[int(str(j)[1:])]*2**j)

Try it online!

Same idea, except the output looks a bit nicer. Numbers don't have leading zeros and the output is whitespace separated.

Python 3, 39 bytes

j=2
while j:j+=1;print([~-2**j%j]*2**j)

Try it online!

This is based on a conjecture that \$2^n\mod n\$ will take all values, except 1, infinitely often. To fix the missing \$1\$, we can compute \$2^n-1\mod n\$, and now \$0\$ will be the missing value.

\$\endgroup\$
1
  • \$\begingroup\$ Your code seems to crash before it outputs any positive integer at all. \$\endgroup\$
    – Wheat Wizard
    Jan 26 at 11:03
1
\$\begingroup\$

JavaScript (Node.js), 29 bytes

n=>parseInt(10+Math.log(n),2)

Try it online!

Like m90's idea, output each number for a time, making it go up to parseInt(k,2), which every number happen for infinite times(10012xxxx for 9, etc.)

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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