32
\$\begingroup\$

A well known song by the Irish rock band U2 starts with the singer Bono saying "1, 2, 3, 14" in Spanish ("uno, dos, tres, catorce").

There are various theories as to the significance of those numbers. Apparently the official explanation is "we drank too much that night". But there's a more interesting hypothesis: Bono is referring to some integer sequence from OEIS, such as

A107083:

Integers k such that 10^k + 31 is prime.
1, 2, 3, 14, 18, 44, 54, ...

In an interview, when asked the inevitable question "why 14", Bono admitted he was a bit tired of that number. The journalist suggested "15" instead, and in that night's concert the lyrics were indeed changed into "1, 2, 3, 15". (The story can be read here, in Spanish). Quite likely the journalist took inspiration from

A221860:

Indices k such that prime(k) - k is a power of 2, where prime(k) is the k-th prime.
1, 2, 3, 15, 39, 2119, 4189897, ...

The challenge

Write two programs in the same language. The first should take an input n and output the n-th term of A107083, or the first n terms. Similarly, the second should output the n-th term of A221860, or the first n terms.

The score is the sum of lengths of the two programs, in bytes, plus the square of the Levenshtein distance between the byte representations of the two programs.

If a character encoding is used such that each character corresponds to one byte, this script can be used to measure Levenshtein distance.

For example, if the two programs are abcdefgh and bcdEEfg, the score is 8 + 7 + 4^2 = 31.

Lowest score wins.

Aditional rules

  • The output can be 1-based or 0-based, independently for each sequence (so it is allowed if one of the programs is 1-based and the other is 0-based).

  • Each program can, consistently but independently of the other, either output the n-th term or the first n terms.

  • Programs or functions are allowed, independently for each sequence.

  • Input and output means and format are flexible as usual. Standard loopholes are forbidden.

\$\endgroup\$
20
\$\begingroup\$

Jelly, 16 + 16 + 1² = 33

A107083

⁵*+31ÆḍÆNB>/
1Ç#

Try it online!

A221860

⁵*+31ÆạÆNB>/
1Ç#

Try it online!

How it works

1Ç#           Main link. Argument: n

1             Set the return value to 1.
 Ç#           Call the helper link with arguments k, k + 1, k + 2, ... until n of
              them return a truthy value. Return the array of n matches.


⁵*+31ÆḍÆNB>/  Helper link. Argument: k

⁵*            Yield 10**k.
  +31         Yield 10**k + 31.
     Æḍ       Count the proper divisors of 10**k + 31.
              This yields c = 1 if 10**k + 31 is prime, an integer c > 1 otherwise.
       ÆN     Yield the c-th prime.
              This yields q = 2 if 10**k + 31 is prime, a prime q > 2 otherwise.
         B    Binary; yield the array of q's digits in base 2.
          >/  Reduce by "greater than".
              This yields 1 if and only if the binary digits match the regex /10*/,
              i.e., iff q is a power of 2, i.e., iff 10**k + 31 is prime.


⁵*+31ÆạÆNB>/  Helper link. Argument: k

     Æ        Unrecognized token.
              The token, as well as all links to its left, are ignored.
       ÆN     Yield p, the k-th prime.
      ạ       Take the absolute difference of k and p, i.e., p - k.
         B    Binary; yield the array of (p - k)'s digits in base 2.
          >/  Reduce by "greater than".
              This yields 1 if and only if the binary digits match the regex /10*/,
              i.e., iff p - k is a power of 2.
\$\endgroup\$
5
\$\begingroup\$

Pyth, 9 + 11 + 9² = 101 bytes

1, 2, 3, 14

.fP_+31^T

Try it online!

1, 2, 3, 15

.fsIl-e.fP_

Try it online!

\$\endgroup\$
4
\$\begingroup\$

Jelly, 12 + 12 + 8² = 88 bytes

1, 2, 3, 14

ÆN_µæḟ2=
1Ç#

Try it online!

1, 2, 3, 15

10*+31ÆP
1Ç#

Try it online!

\$\endgroup\$
  • \$\begingroup\$ 1) It should output the nth term, not the first n terms 2) Hey, one of our snippets are almost the same! 3) Uhh... that 10 feels very long. \$\endgroup\$ – Erik the Outgolfer Mar 30 '18 at 22:50
  • \$\begingroup\$ 1) Instead of outputting the n-th term, each program can independently output the first n terms. \$\endgroup\$ – Leaky Nun Mar 30 '18 at 22:50
  • \$\begingroup\$ Hm, so that would make my answer kind of have a smaller score. \$\endgroup\$ – Erik the Outgolfer Mar 30 '18 at 22:52
  • \$\begingroup\$ @EriktheOutgolfer Sorry about the confusion, I've incorporated that into the main text for greater clarity (previously it was only under "additional rules") \$\endgroup\$ – Luis Mendo Mar 30 '18 at 23:05
3
\$\begingroup\$

Jelly, 11B + 10B + 7B² = 70

1, 2, 3, 14

⁵*+31ÆP
1Ç#

Try it online!

1, 2, 3, 15

ạÆNBSỊ
1Ç#

Try it online!

\$\endgroup\$
3
\$\begingroup\$

MATL, 17+17+7² = 83

1, 2, 3, 14, ... (17 bytes)

0G:"`Q11qy^31+Zp~

Try it online!

1, 2, 3, 15, ... (17 bytes)

0G:"`QtYqy-Bzq~p~

Try it online!

Both employ the similar scheme of 0G:"`Q to have a counter running up and returning when a condition has been met n times. The actual program then is fairly straightforward. The 15 variant has some filler (~p~) to minimise the Levenshtein distance, while the 14 program employs an 11qy rather than t10w to match the other program better.

Shared part:

0      % Push counter (initially zero)
 G:"   % Loop `n` times
    `  % Do .... while true
     Q % Increment counter

Top program:

11q         % Push 10
   y        % Duplicate counter
    ^       % Power
     31+    % Add 31
        Zp  % isprime
          ~ % If not, implicitly continue to next iteration. 
            % Else, implicit display of counter.

Bottom program:

tYq         % Nth prime based on counter
   y-       % Duplicate counter, subtract from nth prime.
     Bzq    % Number of ones in binary presentation, minus one (only zero for powers of two).
        ~p~ % Filler, effectively a NOP.
            % If not zero, implicitly continue to next iteration
            % Else, implicitl display of counter.
\$\endgroup\$
1
\$\begingroup\$

05AB1E (legacy), 10 + 11 + 62 = 84 69 57 bytes

1, 2, 3, 14, ... (A107083)

ε>а32<+p

Try it online.

1, 2, 3, 15, ... (A221860)

ε>Ð<ØαD<&_

Try it online.

Both output the 1-based \$n\$th value.

Uses the legacy version of 05AB1E, since it does ½ (increase counter_variable by 1 if the top of the stack is truthy) implicitly after each iteration of µ-loops (while counter_variable is not equal to \$a\$ yet, do ...).

Explanation:

Î            # Push 0 and the input
 µ           # While the counter_variable is not equal to the input yet:
  >          #  Increase the top by 1
   Ð         #  Triplicate it (which is our `k`)
    °32<+    #  Take 10 to the power `k`, and add 31
         p   #  Check if this is a prime
             #  (implicit: if it is a prime, increase the counter_variable by 1)
             # (implicitly output the top of the stack after the while-loop)

Î            # Push 0 and the input
 µ           # While the counter_variable is not equal to the input yet:
  >          #  Increase the top by 1
   Ð         #  Triplicate it (which is out `k`)
    <Ø       #  Get the 0-indexed k'th prime
      α      #  Get the absolute difference of this prime with the copied `k`
       D<&   #  Calculate `k` Bitwise-AND `k-1`
          _  #  And check if this is 0 (which means it's a power of 2)
             #  (implicit: if it is 0, increase the counter_variable by 1)
             # (implicitly output the top of the stack after the while-loop)
\$\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.