17
\$\begingroup\$

Background

A fractal sequence (Wikipedia; MathWorld) is an infinite sequence of positive integers meeting the following conditions:

  1. Each positive integer appears infinitely many times in the sequence.

  2. Before the first occurrence of a number \$i > 1\$, every number smaller than \$i\$ appears at least once.

  3. Between consecutive occurrences of \$i > 1\$, each number smaller than \$i\$ appears exactly once.

More formal definitions can be found on the Wikipedia and MathWorld pages linked above.

Fractal sequences are named as such because deleting the first occurrence of each number (upper-trimmed subsequence) yields the original sequence unchanged.

A few notable properties:

  • Decreasing all terms by one and removing all zeros (lower-trimmed subsequence) gives another fractal sequence, which may or may not be identical to the original sequence.
  • The signature sequence of an irrational number \$x\$ is a fractal sequence, and it is also identical to its lower-trimmed subsequence. The signature sequence of \$x\$ is defined as: sort the numbers \$i + jx\$ in ascending order where \$i, j \in \mathbb{N}\$, and extract the corresponding values of \$i\$.

A few notable fractal sequences:

  • A002260 and A004736: Count each number upwards and downwards, respectively. These are also ordinal transforms of each other.

    1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5, ...
    1, 2, 1, 3, 2, 1, 4, 3, 2, 1, 5, 4, 3, 2, 1, ...
    
  • A054073: Triangle where the \$n\$th row consists of \$1 \cdots n\$ sorted in the order of fractional parts of each number multiplied by \$\sqrt2\$.

    1,
    1, 2,
    3, 1, 2,
    3, 1, 4, 2,
    5, 3, 1, 4, 2,
    5, 3, 1, 6, 4, 2,
    5, 3, 1, 6, 4, 2, 7, ...
    
  • A122196 and A122197: Count each number down by steps of 2, and count each number upwards twice, respectively. These are also ordinal transforms of each other.

    1, 2, 3, 1, 4, 2, 5, 3, 1, 6, 4, 2, 7, 5, 3, 1, 8, 6, 4, 2, ...
    1, 1, 1, 2, 1, 2, 1, 2, 3, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, ...
    

Challenge

Given a nonempty finite sequence \$s\$ of positive integers, determine if it is a prefix of some infinite fractal sequence. In other words, determine if \$s\$ satisfies the following:

  1. (from condition 2 above) for each number \$n\$ appearing in \$s\$, every number \$i < n\$ appears before the first appearance of \$n\$, and
  2. (from condition 3 above) for each number \$n\$ in \$s\$, every number \$i < n\$ appears exactly once between every consecutive appearance of \$n\$ AND at most once after the last appearance of \$n\$.

For output, you can choose to

  • output truthy/falsy using your language's convention (swapping is allowed), or
  • use two distinct, fixed values to represent true (affirmative) or false (negative) respectively.

Standard rules apply. The shortest code in bytes wins.

Test cases

Truthy

[1]
[1, 1, 1]
[1, 2, 3]
[1, 2, 1]
[1, 2, 1, 3, 2, 1, 4, 3]
[1, 1, 2, 3, 1, 2, 3, 1, 4, 2, 5, 3, 1]

Falsy

[999]
[1, 3]
[1, 2, 1, 3, 2, 1, 4, 1]
[1, 3, 1, 5, 3, 1, 7, 5]
\$\endgroup\$
2
  • \$\begingroup\$ Can we use the integers strting at 0 instead of 1 \$\endgroup\$
    – Jakque
    Oct 15, 2021 at 12:04
  • 1
    \$\begingroup\$ @Jakque No, because the mathematical definition starts at 1. \$\endgroup\$
    – Bubbler
    Oct 15, 2021 at 12:05

9 Answers 9

5
\$\begingroup\$

BQN, 22 19 17 bytes

-3 thanks to Bubbler

-2 by further rearrangement

×∘⊒⊸(/≡∨⊸/)∧⊢≡1+⊐

Try it here.

Explanation:

×∘⊒⊸(/≡∨⊸/)∧⊢≡1+⊐ #
×∘⊒⊸(     )       # Between the sign of the running occurrence count and the input:
     /            # filter (removing first occurrences)
      ≡           # and match against
       ∨⊸/        # the equal length prefix of the input (sorts down the boolean mask, bringing 1's to front)
           ∧      # and
            ⊢≡    # does the input match
              1+⊐ # its classification + 1

Why it works:

Classify () assigns each unique element a number (starting from 0) according to the order of first appearance. That means that if the input matches its classification (+ 1 since starting from 0), every number less than n appears before n, thus satisfying condition 2.

For condition 3, we can use the useful property of fractal sequences that if the first occurrence of each element is removed the result remains the same. Since this is not an infinite sequence we simply check if the remaining sequence is a prefix of the input.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Quick -2: (0≠⊒) → ×∘⊒. (1+⊐)⊸≡∧×∘⊒(/≡∨⊸/)⊢ works at 19 (probably golfable by further rearrangement). \$\endgroup\$
    – Bubbler
    Oct 15, 2021 at 4:49
  • \$\begingroup\$ Thanks! edited it in. \$\endgroup\$
    – frasiyav
    Oct 15, 2021 at 5:06
  • \$\begingroup\$ ⊑×∘⊒⊸/⊸⍷∧⊢≡1+⊐ for 14 \$\endgroup\$
    – att
    Jun 8, 2023 at 5:41
4
\$\begingroup\$

JavaScript (ES6), 52 bytes

Returns false for valid or true for invalid.

a=>a.some(v=>v^=a[~v]^=a[~v]?v-a[j++]&&-1:++i,i=j=0)

Try it online!

Commented

a =>               // a[] = input array, re-used as an object to store
                   //       a 1-indexed ID for each unique value in a[]
a.some(v =>        // for each value v in a[]:
  v ^=             //   test whether v is different from:
    a[~v] ^=       //     the updated value of a[~v]:
      a[~v] ?      //       if this is not the first occurrence of v:
        v - a[j++] //         leave a[~v] unchanged if a[j++] == v
        && -1      //         otherwise: XOR it with -1, which forces
                   //         the comparison with v to fail
      :            //       else:
        ++i,       //         increment i and set a[~v] to i
  i = j = 0        //   start with i = 0 (ID of unique values)
                   //          and j = 0 (pointer in a[])
)                  // end of some()
\$\endgroup\$
4
\$\begingroup\$

Python 3, 91 65 bytes

f=lambda s:s and{*s[-max(s):]}=={*range(1,max(s)+1)}and f(s[:-1])

Try it online!

uses the empty list [] as truthy value and False for falsey

How it works :

  • s and : if the list is empty, return it (truthy value)
  • {*s[:-max(s)]}=={*range(1,max(s)+1)} verify that all numbers are present once in the last chunk of the list;
  • and f(s[:-1]) if the above is True (the last item doesn't contradict the sequence), it tests the list truncated to the last item.

By recursivity, it check that all items are correct

\$\endgroup\$
2
\$\begingroup\$

Jelly, 12 bytes

ṀRḟṣṪṪƊƲƤ⁼W€

A monadic Link that accepts a list of positive integers and yields 1 if a prefix of some infinite fractal sequence, or 0 if not.

Try it online! Or see the test-suite.

How?

Checks that every non-empty prefix contains all integers up to and including its maximum after the penultimate* occurrence of its ultimate value.
* If a prefix only has one occurrence of its ultimate value then the whole prefix is used.

ṀRḟṣṪṪƊƲƤ⁼W€ - Link: list, L
        Ƥ    - for each non-empty prefix, P, of L:
       Ʋ     -   last four links as a monad, f(P):
Ṁ            -     maximum -> M
 R           -     range -> [1,2,3,...,M] = X
      Ɗ      -     last three links as a monad, f(P):
    Ṫ        -       tail -> ultimate value = U
   ṣ         -       P split at occurrences of U
     Ṫ       -       tail -> values after "penultimate" U =  T
  ḟ          -     filter discard -> X without any of T
          W€ - wrap each of L in a list
         ⁼   - equal?
\$\endgroup\$
2
\$\begingroup\$

05AB1E, 18 bytes

Ù0.;0KÅ?IηεÙZLQ}P*

Try it online!

-5 thanks to @ovs

\$\endgroup\$
3
  • \$\begingroup\$ You can remove both Ð and D: the input is implicitly used if the stack is empty and Z doesn't pop the list \$\endgroup\$
    – ovs
    Oct 15, 2021 at 17:55
  • \$\begingroup\$ Å? is a builtin for is b a prefix of a (Iηs.å). If I read the second part correctly, (All prefixes satisify: the unique values are 1..max value/number of unique values), that can be simplified to IÙāQ: 13 bytes \$\endgroup\$
    – ovs
    Oct 15, 2021 at 21:39
  • \$\begingroup\$ @ovs wow thats a total different looking approach, you should post that as a separate answer yourself! (THough i am borrowing the prefix check builtin) \$\endgroup\$
    – Wasif
    Oct 16, 2021 at 7:47
1
\$\begingroup\$

Charcoal, 45 bytes

⬤θ⬤…¹ι∧№…θκλ›⁼№…θκλ⁺№…θ⌕θιλ№…θκι›№θλ⁺№…θκλ№θι

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. - for a fractal sequence, nothing if not. Explanation:

 θ                                              Input array `q`
⬤                                               All values `i` match
   …¹ι                                          Range from `1` to `i`
  ⬤                                             All values `l` match
        …θκ                                     Prefix of `q`
       №   λ                                    Contains `l`
      ∧                                         Logical And
              №…θκλ                             Count of `l` in prefix
             ⁼                                  Equals
                    №…θ   λ                     Count of `l` before
                       ⌕θι                      First `i` occurrence
                   ⁺                            Plus
                           №…θκι                Count of `i` in prefix
            ›                                   And Not
                                 №θλ            Count of `l` in `q`
                                ›               Is greater than
                                     №…θκλ      Count of `l` in prefix
                                    ⁺           Plus
                                          №θι   Count of `i` in `q`
                                                Implicitly print

For a given positive integer i appearing in the input sequence q, each positive integer l<i must pass the following tests:

  • l must appear before the given occurrence of i
  • The number of times l appears before the given occurrence of i equals the number of times l appears before the first occurrence of i plus the number of previous occurrences of i
  • The number of times l appears in total must not exceed the number of times l appears before the given occurrence of i plus the number of occurrences of i

Note that the first and third tests are only useful for the first occurrence of i, but it's golfier to uselessly test them for each occurrence.

\$\endgroup\$
1
\$\begingroup\$

Haskell, 65 bytes

Based on wasif's 05AB1E answer.

import Data.List
f x=isPrefixOf(x\\nub x)x&&[1..maximum x]==nub x

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Scala, 125 bytes

Golfed version. Try it online!

def f(s:Seq[Int]):Boolean=s match{case Nil=>true case _=>s.takeRight(s.max).toSet==(1 to s.max).toSet&&f(s.dropRight(s.max))}

Ungolfed version. Try it online!

object Main {
  def f(s: List[Int]): Boolean = s match {
    case Nil => true
    case _ =>
      val max = s.max
      val range = (1 to max).toSet
      s.takeRight(max).toSet == range && f(s.dropRight(max))
  }

  def main(args: Array[String]): Unit = {
    val testsTrue = List(
      List(1),
      List(1, 1, 1),
      List(1, 2, 3),
      List(1, 2, 1),
      List(1, 2, 1, 3, 2, 1, 4, 3),
      List(1, 1, 2, 3, 1, 2, 3, 1, 4, 2, 5, 3, 1)
    )

    val testsFalse = List(
      List(999),
      List(1, 3),
      List(1, 2, 1, 3, 2, 1, 4, 1),
      List(1, 3, 1, 5, 3, 1, 7, 5)
    )

    for (t <- testsTrue) {
      println(s"${t} => ${f(t)}")
    }

    println("-" * 20)

    for (t <- testsFalse) {
      println(s"${t} => ${f(t)}")
    }
  }
}
\$\endgroup\$
0
\$\begingroup\$

Wolfram Language (Mathematica), 113 bytes

(a=Union@#;f=1>0;Do[f=f∧First@(s=Split[#,#=!=e&])⋂(l=Range@(e-1))==l;(f=f∧l⋂#==l)&/@s[[2;;-2]],{e,a}];f)&

Try it online!

\$\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.