text:
Print/Output all positive numbers in which every multi-digit substring in its decimal representation is also prime.
Task
Your task is to print or output all positive numbers in which every multi-digit substring in its decimal representation is also prime. If the number has at least 2 digits, this would imply that the number itself also needs to be prime.
Example

6197 is in the sequence because every multi-digit substring in 6197 is prime, namely: 61, 19, 97, 619, 197, 6197 (itself).
Note that 6 is not a prime but 6197 is still in the sequence because 6 is not a multi-digit substring of 6197.
8 is also in the sequence because every multi-digit substring in 8 is prime. There is no multi-digit substring in 8, so this is a case of vacuous truth.

Specs

Standard loopholes apply, except that you are allowed to hardcode the output or store information related to the output in your program.
The numbers in the output can be in any order.
The numbers in the output are allowed to have duplicates.
You may use any separator, if you choose to print instead of output.
You are allowed to prefix and/or postfix output if you choose to print instead of output.
The separator and the prefix and the postfix may not contain any digits (U+0030 to U+0039).

Full list (58 items)
1
2
3
4
5
6
7
8
9
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97
113
131
137
173
179
197
311
313
317
373
379
419
431
479
613
617
619
673
719
797
971
1373
3137
3797
6131
6173
6197
9719

Reference

OEIS A131648 (incomplete list)

As always, please feel free to address in the comments anything I should clarify.

For reference, it's 200 bytes simply for the string of digits.

@Dopapp "standard loopholes apply"

I will give +300 bounty to anyone except @Fatalize who submits the smallest answer to this challenge in Brachylog (wiki link) (TIO link) (chatroom).

Poor @Fatalize. That's what you get for creating a language

I have a 50 bytes answer :(

Must the program terminate?

@Fatalize yes, it must.

@LeakyNun Looks like somebody's going to get that bounty!

Brachylog, 18 bytes
9719⟦₁{sᶠℕ₁₀ˢṗᵐ&}ˢ

Try it online!
So...am I ready for the "bounty"? :D

05AB1E, 15 13 bytes
Code:
4°GN§ŒD9›ÏpP–

Explanation:
  G            # For N in range 1,
4°             #   10000
   N           # Push N
    §          # Convert that to string
     Œ         # Get all substrings
      D9›Ï     # Keep all substrings that are greater than 9
          p    # Check each of them if they are prime
           P   # Product
            –  # If 1, print N

Uses the CP-1252 encoding. Try it online! (might take a few seconds).

Brachylog, 18 17 15 16 15 bytes
ℕ₁<l4&≜sᶠ{Ḋ|ṗ}ᵐ

Try it online!
-1 byte after a discussion with Fatalize inspired me to just see what happens if I swap the l and the < around.
This predicate generates the output through the input variable, so long as the output variable is left unconstrained. Since duplicates are allowed, each number is generated with multiplicity equal to 2 to the power of the number of its digits which are prime numbers.
ℕ₁                 The input variable is a natural number
  <                less than
   l4              some number with length 4 (maximized as 9999).
     &≜            Assign a number to the input, and assert that
       sᶠ          every substring of it
         { | }ᵐ    is either
            ṗ      a prime number
          Ḋ        or a single digit.

Older versions:
{≜ℕsᶠ{Ḋ!|ṗ}ᵐ&}ᶠ⁵⁹b
7^₅⟦₁{sᶠ{Ḋ|ṗ}ᵐ&}ˢ
8ḟ⟦₁{sᶠ{Ḋ|ṗ}ᵐ&}ˢ
∧8ḟ>?ℕ₁≜sᶠ{Ḋ|ṗ}ᵐ

This is 16 bytes, but untested, because checking everything up to 40320 isn't exactly fast: 8ḟ⟦₁{sᶠ{Ḋ|ṗ}ᵐ&}ˢ

It terminates fine given an upper bound of 10000 instead, though: https://tio.run/##SypKTM6ozMlPN/r/39AACB7NX/aoqbG6@OG2BdUPd3TVPNw5vfbh1glqtacX/f//PwoA

Brachylog, 18 bytes
Another Brachylog solution. I couldn't get it shorter than Erik The Outgolfer's Brachylog solution; it's the exact same length, but approaches the generation from the opposite direction.
{≜ℕ{sℕ₁₀}ᶠṗᵐ&}ᶠ⁵⁹b

Looks like Unrelated String has beaten this by many a character, whom I congratulate.
Explanation:
{≜ℕ                Brute force all nonnegative integers to find any that match the constraints
   {s               Create a predicate that finds all subsequences of digits of said integer
     ℕ₁₀            Constrains those subsequences to be >= 10
        }ᶠ          Finds all possible values of that predicate: all multi-digit subsequences
          ṗᵐ        Apply a primality constraint to all of those subsequences
            &       Make the predicate output the input integer rather than a prime subsequence
             }ᶠ⁵⁹   Find the first 59 results (all of the puzzle's solutions, and zero)
                 b  Remove the first element of the list, i.e. 0

Try it online!

Jelly, 17 bytes
DẆṖÐfḌÆP€Ạ
³²RÇÐf

My first Jelly answer! Saved 3 bytes thanks to @Leaky Nun!
Try it online
Explanation:
DẆṖÐfḌÆP€Ạ      The helper link, which checks if a given number satisfy the conditions.
DẆ              Convert the argument to a list of its digits and get all its substrings.
  ṖÐf           Remove all lists of length 1.
     ḌÆP€Ạ      Convert back each element to an integer and check if all of them are prime.

³²RÇÐf          Main link.
³²              Create a 100 and square it, which gives 10000.
  R             Create a list from 1 to it.
   ÇÐf          Filter out all the elements where the helper link gives false.

Congratulations on your first Jelly answer!

RÇÐf can be replaced with Ç€T. ṖÐfḌÆP€ can be replaced with ḌḟDÆP.

Java 8, 182 bytes
v->{for(int n=0;++n<1e4;)if(P(n)>0)System.out.println(n);}int p(int n){for(int i=2;i<n;n=n%i++<1?0:n);return n;}int P(int n){return n>99?p(n)*p(n%100)*p(n%1000)*P(n/10):n<10?n:p(n);}

Port of gastropner's C (gcc) answer, so make sure to upvote his answer!
Try it online.
Explanation:
// Loop in range [1,10000), and print any primes corresponding to the challenge description
v->{for(int n=0;++n<1e4;)if(P(n)>0)System.out.println(n);}

// Checks if the given integer is a prime (return unchanged input if prime, 0 if not)
int p(int n){for(int i=2;i<n;n=n%i++<1?0:n);return n;}

// Recursive method that checks if every part of length 2+ is a prime, or is below 10
int P(int n){return n>99?p(n)*p(n%100)*p(n%1000)*P(n/10):n<10?n:p(n);}

PowerShell v2+, 107 104 bytes
1..10+(11..1e4|?{($x=11..($i=$_)|?{"$i"-match$_}).count-eq($x|?{'1'*$_-match'^(?!(..+)\1+$)..'}).count})

Warning: Kinda Slow
Loops from 11 to 1e4 (i.e., 10000) and pulls out numbers using the Where-Object selector (|?{...}). The clause is two components -- the first loops from 11 up to the current number and uses Where-Object to pull out those numbers that form a substring of the current number (via the -match regex operator). We store those substrings in $x. The second portion loops through $x and uses Where-Object to pull out all primes using the prime regex. We then take the .count of both and the check is actually whether those are -equal. For example, 971 will have $x = (71,97,971) and each of those are prime, so 3-eq3 is $TRUE and thus 971 will be selected.
That result is array-concatenated with a range 1..10. The resulting array is left on the pipeline and output is implicit, with a newline between elements by default.

C (gcc), 144 142 140 136 134 132 bytes
-2 thanks to Kevin Cruijssen.
-2 thanks to ceilingcat
...And inspired by that, we can get another 2 bytes from that for loop.
Also shamelessly nicked the rather better prime checker from Kevin Cruijssen's answer for another -4.
p(n,i){for(i=2;i<n;)n*=n%i++||n<10;i=n;}P(n){n=p(n)*(n<99||p(n%100)*p(n%1000)*P(n/10));}f(n){for(n=1e4;--n;)P(n)&&printf("%d\n",n);}

Try it online!

||n<10 can be |n<10 and for(n=1;n<1e4;n++) can be for(n=0;++n<1e4;) for -2 bytes.

@KevinCruijssen Cheers!

Japt, 15 bytes
L²õs f_ã fÅe_°j

Test it

Malbolge Unshackled (20-trit rotation variant), 2,5254e7 bytes or 1,9809e7 bytes
Size of this answer exceeds maximum postable program size (eh), so the code is located in my GitHub repository (note: Don't copy the code using CTRL+A and CTRL+C, just rightclick and click "Save destination element as...").
How to run this?
This might be a tricky part, because naive Haskell interpreter will take ages upon ages to run this. TIO has decent Malbogle Unshackled interpreter, but sadly I won't be able to use it (limitations).
The best one I could find is the fixed 20-trit rotation width variant, that performs very well.
To make the interpreter a bit faster, I've removed all the checks from Matthias Lutter's Malbolge Unshackled interpreter.
#include <malloc.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

const char* translation = "5z]&gqtyfr$(we4{WP)H-Zn,[%\\3dL+Q;>U!pJS72Fh"
        "OA1CB6v^=I_0/8|jsb9m<.TVac`uY*MK'X~xDl}REokN:#?G\"i@";

typedef struct Word {
    unsigned int area;
    unsigned int high;
    unsigned int low;
} Word;

void word2string(Word w, char* s, int min_length) {
    if (!s) return;
    if (min_length < 1) min_length = 1;
    if (min_length > 20) min_length = 20;
    s[0] = (w.area%3) + '0';
    s[1] = 't';
    char tmp[20];
    int i;
    for (i=0;i<10;i++) {
        tmp[19-i] = (w.low % 3) + '0';
        w.low /= 3;
    }
    for (i=0;i<10;i++) {
        tmp[9-i] = (w.high % 3) + '0';
        w.high /= 3;
    }
    i = 0;
    while (tmp[i] == s[0] && i < 20 - min_length) i++;
    int j = 2;
    while (i < 20) {
        s[j] = tmp[i];
        i++;
        j++;
    }
    s[j] = 0;
}

unsigned int crazy_low(unsigned int a, unsigned int d){
    unsigned int crz[] = {1,0,0,1,0,2,2,2,1};
    int position = 0;
    unsigned int output = 0;
    while (position < 10){
        unsigned int i = a%3;
        unsigned int j = d%3;
        unsigned int out = crz[i+3*j];
        unsigned int multiple = 1;
        int k;
        for (k=0;k<position;k++)
            multiple *= 3;
        output += multiple*out;
        a /= 3;
        d /= 3;
        position++;
    }
    return output;
}

Word zero() {
    Word result = {0, 0, 0};
    return result;
}

Word increment(Word d) {
    d.low++;
    if (d.low >= 59049) {
        d.low = 0;
        d.high++;
        if (d.high >= 59049) {
            fprintf(stderr,"error: overflow\n");
            exit(1);
        }
    }
    return d;
}

Word decrement(Word d) {
    if (d.low == 0) {
        d.low = 59048;
        d.high--;
    }else{
        d.low--;
    }
    return d;
}

Word crazy(Word a, Word d){
    Word output;
    unsigned int crz[] = {1,0,0,1,0,2,2,2,1};
    output.area = crz[a.area+3*d.area];
    output.high = crazy_low(a.high, d.high);
    output.low = crazy_low(a.low, d.low);
    return output;
}

Word rotate_r(Word d){
    unsigned int carry_h = d.high%3;
    unsigned int carry_l = d.low%3;
    d.high = 19683 * carry_l + d.high / 3;
    d.low = 19683 * carry_h + d.low / 3;
    return d;
}

// last_initialized: if set, use to fill newly generated memory with preinitial values...
Word* ptr_to(Word** mem[], Word d, unsigned int last_initialized) {
    if ((mem[d.area])[d.high]) {
        return &(((mem[d.area])[d.high])[d.low]);
    }
    (mem[d.area])[d.high] = (Word*)malloc(59049 * sizeof(Word));
    if (!(mem[d.area])[d.high]) {
        fprintf(stderr,"error: out of memory.\n");
        exit(1);
    }
    if (last_initialized) {
        Word repitition[6];
        repitition[(last_initialized-1) % 6] =
                ((mem[0])[(last_initialized-1) / 59049])
                    [(last_initialized-1) % 59049];
        repitition[(last_initialized) % 6] =
                ((mem[0])[last_initialized / 59049])
                    [last_initialized % 59049];
        unsigned int i;
        for (i=0;i<6;i++) {
            repitition[(last_initialized+1+i) % 6] =
                    crazy(repitition[(last_initialized+i) % 6],
                        repitition[(last_initialized-1+i) % 6]);
        }
        unsigned int offset = (59049*d.high) % 6;
        i = 0;
        while (1){
            ((mem[d.area])[d.high])[i] = repitition[(i+offset)%6];
            if (i == 59048) {
                break;
            }
            i++;
        }
    }
    return &(((mem[d.area])[d.high])[d.low]);
}

unsigned int get_instruction(Word** mem[], Word c,
        unsigned int last_initialized,
        int ignore_invalid) {
    Word* instr = ptr_to(mem, c, last_initialized);
    unsigned int instruction = instr->low;
    instruction = (instruction+c.low + 59049 * c.high
            + (c.area==1?52:(c.area==2?10:0)))%94;
    return instruction;
}

int main(int argc, char* argv[]) {
    Word** memory[3];
    int i,j;
    for (i=0; i<3; i++) {
        memory[i] = (Word**)malloc(59049 * sizeof(Word*));
        if (!memory) {
            fprintf(stderr,"not enough memory.\n");
            return 1;
        }
        for (j=0; j<59049; j++) {
            (memory[i])[j] = 0;
        }
    }
    Word a, c, d;
    unsigned int result;
    FILE* file;
    if (argc < 2) {
        // read program code from STDIN
        file = stdin;
    }else{
        file = fopen(argv[1],"rb");
    }
    if (file == NULL) {
        fprintf(stderr, "File not found: %s\n",argv[1]);
        return 1;
    }
    a = zero();
    c = zero();
    d = zero();
    result = 0;
    while (!feof(file)){
        unsigned int instr;
        Word* cell = ptr_to(memory, d, 0);
        (*cell) = zero();
        result = fread(&cell->low,1,1,file);
        if (result > 1)
            return 1;
        if (result == 0 || cell->low == 0x1a || cell->low == 0x04)
            break;
        instr = (cell->low + d.low + 59049*d.high)%94;
        if (cell->low == ' ' || cell->low == '\t' || cell->low == '\r'
                || cell->low == '\n');
        else if (cell->low >= 33 && cell->low < 127 &&
                (instr == 4 || instr == 5 || instr == 23 || instr == 39
                    || instr == 40 || instr == 62 || instr == 68
                    || instr == 81)) {
            d = increment(d);
        }
    }
    if (file != stdin) {
        fclose(file);
    }
    unsigned int last_initialized = 0;
    while (1){
        *ptr_to(memory, d, 0) = crazy(*ptr_to(memory, decrement(d), 0),
                *ptr_to(memory, decrement(decrement(d)), 0));
        last_initialized = d.low + 59049*d.high;
        if (d.low == 59048) {
            break;
        }
        d = increment(d);
    }
    d = zero();

    unsigned int step = 0;
    while (1) {
        unsigned int instruction = get_instruction(memory, c,
                last_initialized, 0);
        step++;
        switch (instruction){
            case 4:
                c = *ptr_to(memory,d,last_initialized);
                break;
            case 5:
                if (!a.area) {
                    printf("%c",(char)(a.low + 59049*a.high));
                }else if (a.area == 2 && a.low == 59047
                        && a.high == 59048) {
                    printf("\n");
                }
                break;
            case 23:
                a = zero();
                a.low = getchar();
                if (a.low == EOF) {
                    a.low = 59048;
                    a.high = 59048;
                    a.area = 2;
                }else if (a.low == '\n'){
                    a.low = 59047;
                    a.high = 59048;
                    a.area = 2;
                }
                break;
            case 39:
                a = (*ptr_to(memory,d,last_initialized)
                        = rotate_r(*ptr_to(memory,d,last_initialized)));
                break;
            case 40:
                d = *ptr_to(memory,d,last_initialized);
                break;
            case 62:
                a = (*ptr_to(memory,d,last_initialized)
                        = crazy(a, *ptr_to(memory,d,last_initialized)));
                break;
            case 81:
                return 0;
            case 68:
            default:
                break;
        }

        Word* mem_c = ptr_to(memory, c, last_initialized);
        mem_c->low = translation[mem_c->low - 33];

        c = increment(c);
        d = increment(d);
    }
    return 0;
}

Performance notes
The application ran about 40 minutes on my machine, producing HEX numbers of the sequence. I stopped it around an hour of calculations, and it finished on 0x11.
Note this answer differs from my other one, because this one actually calculates the numbers, and it can be made so it calculates them indefinitely.
The application allocates the spinup buffer, that is around 7 gigabytes big, so better prepare your free RAM.
Alternative variant
Alternative variant uses around 2 gigabytes of memory less, but produces the output in form of ASCII characters (0 = ASCII(0x0), 10 = newline, etc...), and is available here. It doesn't compete though, due to challenge requirements

Code golf is about giving short answers.

@Alfe Malbolge is a language that was designed to be extremely difficult to program in (wikipedia link); the fact that this is even possible is pretty impressive.

So, in fact, this is a short answer.  Just the standards are shifted.  Slightly.

@Alfe you're welcome to try to shave some bytes off! ;-)

Python 3, 118 bytes
r=range(9720)
for n in r[1:]:all(all(l%k+9//l for k in r[2:l])for l in(n%10**(i%5)//10**(i//5)for i in r))and print(n)

Try it online!
Explanation
Warning: no actual strings involved in this solution.
r=range(9720)
for n in r[1:]:                                        # For each positive integer up to 9720
 all( ... for l in(n%10**(i%5)//10**(i//5)for i in r)) # Check for all its substrings
  all(l%k ... for k in r[2:l])                         # If it is either prime
   +9//l                                               # Or smaller than 10
and print(n)                                           # Then print

C#, 261 249 247 bytes
Saved 12 bytes thanks to Leaky Nun
()=>{Action<int>w=System.Console.WriteLine;int i=0,n,j,k,p,m,b;for(;++i<10001;){n=(i+"").Length;if(n<2)w(i);else{b=1;for(j=1;++j<=n;)for(k=0;k+j<=n;){p=int.Parse((i+"").Substring(k++,j));if(p%2<1)b=0;for(m=3;m<p;m+=2)if(p%m<1)b=0;}if(b>0)w(i);}}};

This compiles to a Func<List<int>>.
The formatted version looks like:
() =>
{
    Action<int> w = System.Console.WriteLine;

    int i = 0, n, j, k, p, m, b;

    for (; ++i < 10001;)
    {
        n = (i + "").Length;

        if (n < 2)
            w(i);

        else
        {
            b = 1;
            for (j = 1; ++j <= n; )
                for (k = 0; k + j <= n; )
                {
                    p = int.Parse((i + "").Substring(k++, j));

                    if (p % 2 < 1)
                        b = 0;

                    for (m = 3; m < p; m += 2)
                        if (p % m < 1)
                            b = 0;
                }

            if (b > 0)
                w(i);
        }
    }
};

Just print it directly without using a list

Instead of false or true, use 0>1 and 0<1

You may refer to this for additional golfing tips.

@LeakyNun Thanks for the tips, I usually like to get a kinda golfed version posted then move from there.

Ruby, 81 + 8 = 89 bytes
+8 bytes for -rprime.
puts (?1..?9*4).select{|m|(r=2..m.size).all?{|i|r.all?{|j|m[i-2,j].to_i.prime?}}}

See it on repl.it: https://repl.it/CniR/2

Perl 6,  47 44  43 bytes
for 1..9719 {all(m:ex/..+/).Int.is-prime&&.say}
put grep {is-prime +all(m:ex/..+/):},1..9719
put grep {is-prime +all m:ex/..+/:},1..9719
Explanation:
# print the values space separated, with trailing newline
put

# that match
grep -> $_ {

  # call the method ｢.is-prime｣ ( that is what ｢:｣ is for )
  # (autothreaded)
  is-prime

  # convert following to numeric (autothreaded)
  +
  # a junction of
  all(
    # all substrings 2 characters or greater
    $_ ~~ m :exhaustive / . .+ /
  )

  # needed to indicate that ｢is-prime｣ is a method call
  :

},

# in this Range
1..9719

JavaScript (Node.js), 130 bytes
if i can assume infinite stack i*i<=n&& can be removed and i*i>n turns to i>=n which reduces the code by 9 bytes and maybe convert main function to recursive : https://tio.run/##LYpBDoIwEEX33AMyAxVbXUmccgX2xkWDRYeQaSPqyrvXkrj5ef/lze7j1vHJ8bWTcPMpTQRMWjm6XJFs0/DZ@EM/ASunBmCsKtfG9/rIiJ0rIoEoJpNbKXPdx@1jx5akGEiytqdNYp2nNFr/wR@xHkD2Rn81dpLGIGtYfLuEO0yAmH4 (119 bytes)

_=>eval(`for(a=[i=1];++i<1e4;)P(i)&&a.push(i)`)||a
p=(n,i=1)=>i*i<=n&&n%++i?p(n,i):n%i
P=n=>n>9?p(n)*p(n%100)*p(n%1e3)*P(n/10|0):n

Try it online!

Swift 4, 144 bytes
let p={n in !(2..<n).contains{n%$0<1}}
print((1...971).filter{$0<10||p($0)&&($0<100||p($0/10)&&p($0%100))}+[1373,3137,3797,6131,6173,6197,9719])

Try it online!
Explanation
let p={n in !(2..<n).contains{n%$0<1}} // Helper function p, tests if a number is prime
print((1...971).filter{                // Print every number n in the range 1 to 971
 $0<10                                 //  that is less than 10
 ||p($0)&&                             //  or a prime and
 ($0<100                               //   is less than 100 or
  ||p($0/10)&&p($0%100))}              //   n/10 and n%100 are primes
+[1373,3137,3797,6131,6173,6197,9719]) // Print the four digit numbers

Malbolge, 1361 bytes
Simple and boring version. Displays numbers from the highest.
D'`r^"!=[YG3yUCvA-csNqp-nJ$HYFgDC#AbQ,|*)\rwvutm3kSonmlkdihg`&dc\aZ_X|V[ZYXQPt7SRQPOHGkKJIHG@d>=<A:98\}|:981U5.-2+0/.'K%$#G!E}e#z!~}v<]yxwpun4rkj0nmfN+ihaf_^$\a`_XW{>=YXWVONrLKPINGkE-IBAe(>=<;_?>=}|:3W1w543,P0).-&J*)(!E}|B"!~}|{zyr8potml2jongfkjibg`&d]\"`_XW{>=YXWVONr54JIHMFj-,HGF?>b%A@?87[;:981w543,P0).-&J*j(!EfeB"!~}_u;yrqpun4rqpihmlkjihg`&d]\"`_X|\[ZYXQuUNMLQJnH0LKJIBAe(>=<`#"8\<5Y9270T43,Pqp.-&J$)"!~D|#"y~}|u;s9qvotsrk1inglkdihg`&d]\"Z~XWVUZYXQu87SLKo2NGFjDIHGF?>bBA#"8\6;:981Uv.32+*)Mnm%$)('~D|{A!xwv{zyr8vXnsrkjoh.fNdchg`ed]#aC_^WVz=YXQPt7SRQPOHGkK-IHGF?>bBA#"8\6;:981Uv.32+*)Mnm%*#"F&%$#cy?}v<]\xwpun4rqSonmf,diha'eG]#a`_X|V[ZYXWPt76LKoIHGLEiCHGFED=aA:?>7[;:981w/4-,PO)o'&J*j(!E%edz@~}_u;yxqpo5mrqpoh.f,jibgf_%]\[!_XW{[ZYXQu87SLKo2NGFjJIHAF?c=BA@?>=<5Y38765.-Q10)o'&J*j(!E%e{z@~}|{ts9qpotsrk1oQglkd*)gIed]#DZ_^]VzZYRQuONMRKJnNGLEJCgG)(D=aA:?>=<;4X816/43,P0).-&+$H('gf|Bcb~w|u;yxwYutmrqj0nmleMib(fH%cba`_X|VUZYXWPt7SRQPOHGkEDIHG@dDC<;@?8\6|:32V0T43,+O)o'&J*)('&}C{"yxwv<tyr8vun4Ukpoh.fN+c)gIed]#DZ_^]VzTSRWPtTSLQJnH0LKJIBAe(>=BA@987[;:381Uv.32+*)Mnm%$)('~D${"y?}_uzyxqpo5srqSonmf,jihgfeG]#a`_X|V[ZYXWPt76LKo2NGFjJIH*)ED=a;@?>76;4X816/43,P*).',%I)('~Ded"y~}|u;srqvo5mlqpih.fN+cba`&d]\aZ~^]VUZSwWPUTSLpJ2NGLEiCHGFED=a;:?>7<5YX876v43,+O).-,+$H('&feBz!x}v{zsr8punsrk1inglkdihg`&d]\"Z~X]V[ZSwQVUTMRKo2NGFjDIHGF?>b%A@?87[;{921U5.3210)M-,%k#(!EfeB"y~}v{zyr8%

Try it online!

TI-83/84 BASIC, 124 Bytes
For(A,1,E4
DelVar Nint(log(A→P
Ans→Q
While Ans
For(I,0,Q-Ans
10^(P+1
AnsfPart(iPart(A/10^I)/Ans→S
min(Ans={2,3,5
If S≥7 and fPart(.5S
min(remainder(S,3+2cumSum(not(binompdf(int(.5√(S)),0
N+not(Ans→N
End
P-1→P
End
If not(N
Disp A
End

Loops over the first 10k integers.  Sets up a counter in N to check each substring prime, and int(log(A retrieves one less than the number of digits in the current number.  We then set that number aside in a second variable so we can step P down through each length substring at least 2 digits. 10^... and AnsfPart(iPart(,,, generate the current substring to check for primality, then the following 3 lines do the primality check to 1 or 0 in Ans.  If the substring is not prime, we increment N, and after all the substrings are checked if N is still 0 we print the current number.
Possibly some tweaking could be done to increase the efficiency of the primality check toward this test?  I'm just glad I found an algorithm in fewer bytes than storing the output directly in TI-83 formatting!

Python 3.8 (pre-release), 194 bytes
r=range
s=str
l=lambda _:len(s(_))
[*map(print,[t for t in r(1,10**4) if all(all(int(x)%b for b in r(2,int(x))) for x in [s(t)[i:j+1] for i in r(l(t)) for j in r(i,l(t)) if l(s(t)[i:j+1])>1])])]

Try it online!

PHP, 135 bytes
for(;++$n<1e4;$p||print"$n
")for($p=$i=0;$i<$l=strlen($n);$i++)for($j=1;$j++<$l-$i;$p|=$k)for($k=($m=substr($n,$i,$j))-1;$k&&$m%$k--;);

Try it online!
for(;                         // level 1 loop on
  ++$n<1e4;                   // all numbers from 1 to 10,000, $n is current number
  $p||print"$n\n"             // at the end of loop for each number, print $n if all multi digit sub strings were prime ($p=0)
)
  for(                        // level 2 loop on each digit of $n
    $p=                       // $p is a flag for all sub string primes and is set to 0 for each new $n
      $i=0;                   // $i is position of current digit (and sub string start position)
    $i<$l=strlen($n);         // $l is the total digits count in $n
    $i++                      // increment $i by one
  )
    for(                      // level 3 loop to create sub strings
      $j=1;                   // $j is length of sub string, we only care about multi digit sub strings so it starts from 1
      $j++<$l-$i;             // continue the loop as long as $j has not reached last digit and increment it by one
      $p|=$k                  // THIS IS RUN AFTER LOOP LEVEL 4: update $p flag based on value of $k
                              //     $p will be left at 0 only if all of the sub strings are prime (if $k is always 0)
    )
      for(                    // level 4 loop to check each sub string to be prime
        $k=(                  // $k is set to current sub string minus 1
          $m=substr($n,$i,$j) // $m is current sub string
        )-1;                  //
        $k && $m%$k--;        // as long as $k is more than 0 and $m%$k is not zero, decrement $k by one and continue
                              //     a prime number will only get a 0 remainder, when $k gets to 1
                              //     so $k will be 0 for primes and more than 0 for non-primes
      );


text:
Identify a string from its substrings
Introduction
I've previously created two challenges where the idea is to reconstruct an object using as few query-type operations as possible; this will be the third.
The task
Your inputs shall be a non-empty string S over the alphabet abc and its length, and your output shall be S.
With no restrictions, this would of course be a trivial task; the catch is that you're not allowed to access S directly.
The only thing you're allowed to do to S is to call the function num_occur(T, S), where T is some other string, and num_occur counts the number of occurrences of T in S.
Overlapping occurrences are counted as distinct, so num_occur(T, S) really returns the number of indices i such that
S[i, i+1, …, i+length(T)-1] == T
For example, num_occur("aba", "cababaababb") will return 3.
Note also that num_occur(S, S) will return 1.
The result of num_occur("", S) is undefined, and you should not call the function on an empty string.
In short, you should write a function or program that takes S and length(S) as inputs, calls num_occur on some shorter strings and S some number of times, reconstructs S from that information and returns it.
Rules and scoring
Your goal is to write a program that makes as few calls to num_occur as possible.
In this repository, you will find a file called abc_strings.txt.
The file contains 100 strings, each on its own line, between lengths 50 and 99.
Your score is the total number of calls to num_occur on these inputs, lower score being better.
Your solution will preferably keep track of this number as it runs, and print it upon finishing.
The strings are generated by choosing uniformly random letters from abc; you are allowed to optimize for this method of generating the strings, but not the strings themselves.
There is no time limit, except that you should run your solution on the test cases before submitting it.
You solution should work for any valid input S, not just the test cases.
You are encouraged to share your implementation of num_occur too, if you're not using someone else's.
To get the ball rolling, here's an implementation in Python:
def num_occur(needle, haystack):
    num = 0
    for i in range(len(haystack) - len(needle) + 1):
        if haystack[i : i + len(needle)] == needle:
            num += 1
    return num

Does our algorithms have to work for all possible strings S, or just for the test cases?

@Loovjo Good question. They should theoretically work for all non-empty strings. I'll edit the challenge.

all non-empty strings of whatever length?

@edc65 Theoretically yes. You can ignore bounded memory addresses and other practical limitations.

It is possible to add a VW algorithm to pass the evaluation test with success: Check first for occurrence of the known strings of abc_strings.txt

@Emmanuel No. That would be optimizing for the specific test cases, which is forbidden.

Javascript, 14325 14311 calls
We start with an empty string and go our way recursively by adding a new letter at the end or at the beginning of the current string while we still have at least one match.
All previous results from numOccur() are saved in the sym object and we use this data to reject immediately any new string that can't possibly be a candidate.
EDIT: Because we always start with 'a', we always know the exact number of a in the string. We use this information to end the process earlier when we detect that only a sequence of a is missing. Also fixed the regular expression which was invalid in Chrome and IE.
var test = [
  'ccccbcbbbbacbaaababbccaacbccaaaaccbccaaaaaabcbbbab',
  // etc.
];
var call = 0;

function guess(S, len) {
  var sym = {};
  recurse(S, len, "", sym);
  return sym.result;
}

function recurse(S, len, s, sym) {
  var dictionary = [];

  if(s == '' || (isCandidate(s, sym) && (sym[s] = numOccur(S, s)))) {
    if(s.length == len) {
      sym.result = s;
    }
    else if(sym['a'] && count(s, 'a') == sym['a'] - (len - s.length)) {
      dictionary = [ Array(len - s.length + 1).join('a') ];
    }
    else {
      dictionary = [ "a", "b", "c" ];
    }
    dictionary.some(function(e) {
      return recurse(S, len, s + e, sym) || recurse(S, len, e + s, sym);
    });
    return true;
  }
  return false;
}

function isCandidate(s, sym) {
  return sym[s] === undefined && Object.keys(sym).every(function(k) {
    return count(s, k) <= sym[k];
  });
}

function count(s0, s1) {
  return (s0.match(new RegExp(s1, 'g')) || []).length;
}

function numOccur(S, s) {
  call++;
  return count(S, s);
}

test.forEach(function(S) {
  if(guess(S, S.length) != S) {
    console.log("Failed for: '" + S + "'");
  }
});
console.log(call + " calls");

Full executable snippet below.

var test = [
  'ccccbcbbbbacbaaababbccaacbccaaaaccbccaaaaaabcbbbab',
  'caccbbababbaaaccbcabbaabaabcacabacaababcabcbbacaac',
  'bbbbaacabcabacaccaaaabaaacaacabbcbacabaccbbcbabbcbc',
  'abbcbcbccbccaacaccaccaabaccbbcabaaccabccbbbabbbcabc',
  'aabacbbbcaaabcccaccccbcaabcacaccbabbbcccacabaaababca',
  'bccbbaaccaaccacabaaaabbbbaababacabaaabacbcacbbbbabaa',
  'bbbcbcabbacbaacbacabcbabbacacbbcbcabbaabbbccbacaaacac',
  'ccbcbbbaaaaaccbaacbabbbcbccbabaabccbcbcbcbabcbbccacba',
  'aacbcbcabcbcbccbabbacacbcaaababbbcacaacaccbabbbbabcaac',
  'bcabacaabbacccacaabcaaacbcbcbacabbababcabbbbacbaaaabbb',
  'abbaccccabbbcbbaacccacbcaacababaccabbabbacbbbaabaacbaba',
  'cabbacabacccabcabacbaacbaababcaccbacbaaaacbbabbbccabbbb',
  'bcabccaaabcbaaccaabccbbcbabaccababbbaccccacaaccaccacbcab',
  'abbcbabaacbcbbabbccccbccabcbbaccacbabcacbaacbccbcabcccbc',
  'bcbacabbaabcccabccacbcbccbcbbbccacbbccaabaacccccbcabaaccc',
  'baccbcacaccacbbbcccbaaacbaccacbbacbbbaccccacbabcbbbaacabb',
  'bcccabaaaabcbbbaaccbcaccbaabacccaaacbaabaccccacabaccacbcac',
  'baabcbbcaabcacbabbcacccbcabbabaacbbbababbbbbccccccbcbbcbcc',
  'bacacbbabbcbbcaacabcccccbbacabcaabbbcbbabaacbcbbaccaaacbbac',
  'ccabccbccbaaacbcccccabacbbabbbbccbccccabaabaabbaacbabcabbcb',
  'abbaccbcaabacbbacabaabbcbacbacacabccbbcccaccbbacbbbaacbaccab',
  'bbbbaaabababcccbbbababacbacbaabbabccacccaaacabaccababaccbcac',
  'bbcbbbbcccaccbbbcbcaaccbcacaabbbbabaaabbbaaacbbaaccbacaccabbb',
  'cacabcabcbcbbbbcabbbccccccccacaaabaacbcaabbabcacbcbcccccacaab',
  'babbcacabaabbccabcbbaacccaaccbabcbbcbcbbbcabbcccbcacbabccaccac',
  'ccbbcbcbcaacbcaaccacbcaabbbcbbaccbbabacacccccaccaababcacccccba',
  'bcccbcacccccabccabccbcbccaccaaacbcacabaabcbcccaccaaaabbcacbbcaa',
  'cbbcacbbacaacbabccaabbaabacacbcbcbabcaccabbbbcabbbabaaacccaabcc',
  'aabbaacccaaacbcaabcabaabbbaababbbbcbacabbbbbbbbccaccccbbaccbbaaa',
  'abbcccabbabbaccccaacbabbccccbbbbccaaacaabacbabbabcabacbaabcbcacb',
  'bcacbccccaacbbcaccbcbcbbabacabacabbcaaabbccabcccbaacabcbbcacababb',
  'acabacaabcabbcccccbcacaccccbccaaaacacbbbccbcaabaacbbbacabcbcaabca',
  'caabbaccaacbbcbaacbcabccacacabbcbcbbacabbbaacccaacccabaaaccbbacbaa',
  'baaabbcbbbaacabacbcaaacabbacaacbacabbcabcccbabcbbacacbbababccacabc',
  'abbbacbaabcabbcabbbabaababbaabcacbabbaababcabbbccccbcaacbbcccabaccb',
  'caaababcacccaccababaccbabbccaabbbbbabaabcabccbabbbbbbcbacbabcbcccbb',
  'abbbcaaaaacaaacbbbcbacabbcbbbccacaccacacabacacbbccbbbcbaccabbcbaabbc',
  'bacacbcccabcabaabacccbcaaabcabbbcccaacbabacbaabbcccacaacbabbcacbaabb',
  'bacaaaccbaababbbbbcaabcabaacccabacccbabcbccbbcbcaacbbaabcaccaaaacaabb',
  'bbacaacccaaacacccbbacbcbbaaaccccabbbbcbbbabaaaaccbccaababaccbbccacaca',
  'aacccccbabaccbcbcbbaccbacbcbacaababaaaccbaaabaabcccccacbbaabcccaababcc',
  'babacacbbbacbbbbbabbabababacabacaaacbbccaccabacaacbabbbaccacccbcaaabbb',
  'bcaccabbabbcbcabccbbcaacbbcbacbcabaaaaaacaaacaccbcaaccaaccacbaccacaabbc',
  'acbcbbcbbaacbbbabbaabacabbcccabacabcabacccacbcaacacabcaaaabbabcccbcbabb',
  'ccbcbcccbccbbbabaabbaababbcbacacbcbaacaccccccbcbacacbcabaaaacaacbbbbacba',
  'cccbcbaaabcbbcbabbbaccabbabcacbaccbcababbababcbcaccabbbccabaabaaccccacbb',
  'bbabcbcaabbacaabcababbbccbccccaaaabaccbbbbababbcabbabbaccaaaabbcbbbcbaccc',
  'cbacaccaaaacaacbbcbbacaccabacaacacaacaacabccaaaccccacaaaaabcbcabaabaacccb',
  'bcacbccabcccabababbbbcabaacabcbbaacaaaabbbacccaaabccbaabcbbabbbcccabaabbbb',
  'cbccacabaaacabbccbacabccacabcbaccbababcccabbabbbbbbccbaabbaacaacaaaabcbabb',
  'abcbcabbcabaababccbcacabbcbcabcaabbbabbcaaabaaaaacbaabaaababccacbabcbaccbab',
  'aabbabbbcacaaaabcbcabccccacbacbccacacaabccacccaaacacbcccaabbbccacacbbccbbac',
  'caacbbccacaaaacabaacbcaaaccbbabbcacababbbabcbccbaabccaababbcbacbccababbcbbbc',
  'aaabaaaabbbbbcbbbacabccbaaaaabaacbacbcccbccacccacaaacaccbbabcbcccbbccccabbcb',
  'cccccacacbacbbcbbcabcbaabbcbbbacabcbbccccaaacabcababbcaaccaabccabaccbcaccbaba',
  'ccaaaccbccacabcacaccbccaabacacabaabbbaacbcacaacbaaabbbbabbabcccabcabbaccacacc',
  'cbbbcaccbcacccbacccaaaabacaacccbcbcbabbbaababacccccccabbaaabbcbaabbbbbbaaaaaaa',
  'ccbcbcbaabbccabbabbccbacbabacbcacbccacaabbcacaaccabbbbcbacbbcaaabaabccaacccacb',
  'caaabcabaacbbabcbccabcacbbcccabcacbbcaabaacaaabbbcacaaccaccaaaacaaccbbaaaacaaac',
  'bbacacbbaaaacbcabbbbbaabacaccabcbabbccbbbabbbacccababbcababcbbcacbababbbaaabcca',
  'bbacbbacacaccccbabbbbcabbcccbcacaabbcabbccaaaaabcbbcccaccbcbbbccabcbaccacbacbaba',
  'baccbcababbacabcbabacaababbaabcabbcbcbccabacbbaaaaabacaaacaacbacbcabacabaaccbcab',
  'accacccabccbabcbcbaababacabcabbcaccbccabbabcbcabbaabccacbbbbcaacbccaababbababbaba',
  'bbcccbcbcbccccbcaaccaaacacbbaacbcccbbcabbbccabaacbacaaaccbcbaacababaccacbcbaaccac',
  'acbccccaabcabbbcbbccbccbacbcabcccacbcabbaacbababbbcbbccacbacccbbbaccbaaaabbbabaccb',
  'babcacaccbccbaaabaabbbaabcaabaaccccacaacbaccbcbabbbbbbabcbbbbacbacbabcbbbacbbbbbbc',
  'caabcaaaaabacccacbbbaabaabccaabcbaabbcbcbbbccbabbccbcbabbbbccacbcbcbacaaccccacbbabc',
  'bbaaabbabccaccacbcbbccaaaaababbacccbabcbacabacbaacbcabaaacacaaaaacaaacabbbbccabbbca',
  'bbcbccababbbaabbabcbbaacbccbaacbababbabcbaaccbcbcabacaabacaacabcababbaaabbbbbbccccbb',
  'acabcabccaaccccacbcaabaccacaaabcbabbabbaccbbaaacacabcabbcabababaccccbcbabaacbbcccbab',
  'bacaaaaacbcacbbbaaaaabbbbcbbcbbbcaccccbacaccbbcbabbbccbaaabbcbaccacacbcbcacbcbaaabacc',
  'bbcaabccbcaccbabbacbaacacccccaabbbccbccbbbcccbacaaaccccbccbbbbabccaaacaabbbbacaacabab',
  'aaaccccbbabbcacabaacacbabbcacbcccbcbaaacaabaabacbbaabcbbbbbcacbaccaacaacbccacbbcacbbaa',
  'bbcacabcbbcbabbabbbacaaabcabbbbacbacbabacbbbbbabacabbabaabcabbaabbbaaccbcabcababcaaacc',
  'ccccbaacbbcaccaccbaaacaccbabbabaabbababcacacaaccbbcbccaaaaaaacbccacbacbabbbabcabaabaabb',
  'abacacbaccacaaacaccbcbabcaacbccaccbbacbabcababcaabcaabcbcabbcbacabaaaaaabaccccbbbcbabac',
  'ccccacbaaabaaacabbabacbbacbabcbbcaaaaacaccacabcaacabcbcbcaccabcaaccbaccabcccbccacccbacbc',
  'bcaabcaacacccbcababccacacbccccccbbaaabacabbcbbbcbaaacbbacababbaccccacbbcbacaacbabcbaccbc',
  'cbcbbaabacbaacbbcabbbbaccbaabbacbcccaaabbabacabbbababcaabcacbaccacacaccbbbbcbcbbaaacbcbba',
  'ccbcabcaabcbabbbcbcbbabacabacbbaccbbcbcabcaccaaccbaccbaacacacbbaacaaaaabcaaaacbcccbcccaaa',
  'cbbababacbbabbabaabaaaabcacbacbcccbacbccbbcaabcabaccacccbbcaacacccccaccabaabccacbaccabaaba',
  'cbbbaaacaccbcabccacbccabacbcbcccccacaccbbcccbcbbbaababcaaaacaabbbccbacbaccabccccbbbcaaaabb',
  'bbabbacaaccacccbbcabbacbcbabcccaccacbacbccababbbcacbabbbcabbbbacabcabcbaacbaabcbccacaaaccbc',
  'babcbaabccabcabaaabcaaaabaaaaccbcbcacbbbccaccccaacbcbabbbaaaccacaaabacbbabbcacbcaaaaabaabab',
  'acbabbccacaccabccbcbabacccbabbaacbccbcaabccbcbababccacbbbaabbaaaababbcaaaaabccbacbbcacbcacba',
  'cbccbbaacacccacacacbbbcbbccabcaaaabbcacacacaccbacaacbcbcbccaacaaaaaacbacacbabbbcccabbbbababa',
  'cabaabaccbbcccabaccbbacbcabbbbbaccccccbcbcbcbbccbaaabbbbcabacabccaacbcbcbabccbbcabacababccaab',
  'bccaacbabcbccaccbabcbbcbaaccbaacabbcabbbacbbccabcabccabccbacbaacbccabccaabaaabcaababacacccaac',
  'aacabcccaaccacbbcbbbbacaacacbcbcaabbcbbacbabcbccaabcbbbbaabccbbbacaababcabaacaccababacbcbccbba',
  'caaabbcbcbcabccccacacaaababbacbabacbaaccbcbabbaaacbbccccaaaabbccbcabcbccbbaaccbbbabcaabcbbbcab',
  'aacbbcbbcbaccccbaaaabcbaaabaaacaacaaacacacabaaabacbaaaacccbaaabbbcbbbacbcbccabccaabbaabcbcbccba',
  'abaccbcacabbbbacabaacaccbcbaabbaccaabbbbbababbbcbbbbacaacabbbabcaccbacabbabcbbacbbaaccbcbacaabc',
  'aacaaaacccabcccacacbaaccccababcaccaccacbbbacabccbbcbbbacaccbbbbbaabacbacbcbcabccaaccababacaabcbb',
  'baabbabaaccabcbbabcacccccaabbccbccbcaacbbbccccbbcbacaabcccccbbabbabbcacbbccbcacabbbbaaaaccbcacca',
  'aabacbaacbbccabbbacbcbbbabacaacccabbcabacacaaaabbcbbbcbbbcababbccbbacbbabcaacbacbbcaabbbcbaaaccaa',
  'aacabaaccaaabcacccabbaabbcacbabccacabaccaaaaccccccaabcbbbaabcbcccacaccbcaaacaaaabaababccbbbcccaac',
  'bcaccbcacaccbacbcccbcbbcabaabbabcccbaaababbbabbcbcbcaabbabbccccbabccabbccccabaaabccbacabccabbbacaa',
  'ccaacbabcccbabacabaccccbcbbcccbbbacbbbcccacababccbbaaaaababbabccbccabcccbccabaccbcbcacbbbaacabccaa',
  'caccbababcbcbabccabcbbaccbbbabcbacbcbcbcabcbacbcacabbcaabbbbbbbcbbaabcacccbcaabccacbccbbcccaabcbcac',
  'bbcccaabacbacbccbbbbbaabccaaabbaabcaabbcbabbbaabcbcbacbaccabacacaaaababccaaaccacaabaabcacbcaccbaabb'
];
var call = 0;

function guess(S, len) {
  var sym = {};
  recurse(S, len, "", sym);
  return sym.result;
}

function recurse(S, len, s, sym) {
  var dictionary = [];

  if(s == '' || (isCandidate(s, sym) && (sym[s] = numOccur(S, s)))) {
    if(s.length == len) {
      sym.result = s;
    }
    else if(sym['a'] && count(s, 'a') == sym['a'] - (len - s.length)) {
      dictionary = [ Array(len - s.length + 1).join('a') ];
    }
    else {
      dictionary = [ "a", "b", "c" ];
    }
    dictionary.some(function(e) {
      return recurse(S, len, s + e, sym) || recurse(S, len, e + s, sym);
    });
    return true;
  }
  return false;
}

function isCandidate(s, sym) {
  return sym[s] === undefined && Object.keys(sym).every(function(k) {
    return count(s, k) <= sym[k];
  });
}

function count(s0, s1) {
  return (s0.match(new RegExp(s1, 'g')) || []).length;
}

function numOccur(S, s) {
  call++;
  return count(S, s);
}

test.forEach(function(S) {
  if(guess(S, S.length) != S) {
    console.log("Failed for: '" + S + "'");
  }
});
console.log(call + " calls");

"In short, you should write a function or program that [...], reconstructs S from that information and returns it."

@KarlKastor - Oops. You're right. That's fixed. Thanks!

Python 12705  12632 calls

make a list of 2 characters strings occurrences
sort the list
build the string trying the most probable character first, don't test if there is only one possibility
update the list
if the list is empty it is finished else step 2

I used Loovjo function skeleton. I never code in Python I needed a bootsrap
EDIT:
Added code for one character length strings
Added code to reject already matched patterns
def finds(S):

    if len(S) == 0:
            return ""
    if len(S) == 1
            if num_occur("a",S) == 1 :
                         return "a"
            if num_occur("b",S) == 1 :
                         return "b"
            return "c"
    tuples=[]
    alphabet=[ "aa", "ab", "ac", "ba", "bb", "bc", "ca", "cb"]
    for s in alphabet : tuples.append( (num_occur(s,S), s) )

    sum=0
    for (i,s) in tuples :   sum+=i
    tuples.append( (len(S)-sum-1, "cc") )
    tuples.sort(key=lambda x:(-x[0],x[1]))

    (i, current) = tuples[0]
    tuples[0] = (i-1, current)

    add_at_start = True
    nomatch=[]
    while len(tuples) > 0:
            worked = False
            tuples.sort(key=lambda x:(-x[0],x[1]))
            count=0
            if not add_at_start :
                    for (n, s) in tuples :
                            if s[0]==current[-1:] :         count+=1
            for i in range(len(tuples)):
                    (n, s)=tuples[i]
                    if add_at_start:
                            if current[0] == s[1] :
                                    current_new = s[0] + current
                                    possible=True
                                    for nm in nomatch :
                                            lng=len(nm)
                                            if current_new[0:lng] == nm :
                                                    possible=False
                                                    break
                                    if possible and num_occur(current_new, S) > 0:
                                            current = current_new
                                            worked = True
                                    else :
                                            nomatch.append(current_new)
                    else:
                            if current[-1:] == s[0] :
                                    current_new =  current + s[1]
                                    possible=True
                                    for nm in nomatch :
                                            lng=len(nm)
                                            if current_new[-lng:] == nm :
                                                    possible=False
                                                    break
                                    if count == 1 or (possible and num_occur(current_new, S) > 0) :
                                            current = current_new
                                            worked = True
                                    else :
                                            nomatch.append(current_new)
                    if worked :
                            if n == 1:
                                    del tuples[i]
                            else    :
                                    tuples[i] = (n-1, s)
                            break
            if not worked:
                    add_at_start = False
    return current

no 'cc' in your alphabet?

@Sparr "cc" is calculated, that's saves 100 calls : tuples.append( (len(S)-sum-1, "cc") )

Python, 15205 calls
def findS(S, len_s, alphabeth = "abc"):
    if len_s == 0:
        return ""
    current = ""
    add_at_start = True
    while len(current) < len_s:
        worked = False
        for letter in alphabeth:
            if add_at_start:
                current_new = current + letter
            else:
                current_new = letter + current
            if num_occur(current_new, S) > 0:
                current = current_new
                worked = True
                break
        if not worked:
            add_at_start = False
    return current

This submission is most likely suboptimal, because it only uses num_occur to check if a string is a substring of S, and it never uses it to actually count the amount of substrings.
The algorithm works by storing a string current which is built up to be equal to S in the end. Here are all the steps in the algorithm:

We set current equal to ''
Go through each letter in the alphabet, and do the following:
2.1. Create a new string current_new, and set it equals to current followed by the letter.
2.2. Check if current_new is included in S by running num_occur on it and see if the result is greater than one.
2.3. If current_new is included in S, set current to current_new and go back to step 2. Else, we go to the next letter.
If the length of current is equal to the length of S we can say that we are done. Else, we go back to step 2, but modify step 2.1 to make current_new equal to the letter followed by current instead. When we reach this step again, we are done.

Python's for loop has an else clause. This would be a perfect use case for it.

Python 2, 14952 14754 calls
Very similar to the first answer, but doesn't try next characters which result in impossible substrings that:

we know from num_occur that they don't occur in the target (from previous calls)

we already used the substring more often than it occurs according to num_occur

(will add counting of substrings in a minute) done
def get_that_string(h,l,alpha = "abc"):
    dic = {}
    s = ""
    ##costs 1 additional call per example, but its worth it
    char_list = [num_occur(j,h) for j in alpha[:-1]]
    char_list.append(l - sum(char_list))
    for y, z in zip(char_list,alpha):
        dic[z] = y
    end_reached = False
    while len(s) < l:
        for t in alpha:
            if not end_reached:
                neu_s = s + t
                substrings = [neu_s[i:]   for i in range(len(neu_s))]
            else:
                neu_s = t + s
                substrings = [neu_s[:i+1] for i in range(len(neu_s))]
            ## Test if we know that that can't be the next char
            all_in_d = [suff for suff in substrings if suff in dic.keys()]
            poss=all(map(dic.get,all_in_d))
            if poss:
                if not neu_s in dic.keys():
                    dic[neu_s] = num_occur(neu_s,h)
                if dic[neu_s] > 0:
                    s=neu_s
                    for suff in all_in_d:
                        dic[suff] -= 1
                    break
        else:
            end_reached = True
    ##print s
    return s

## test suite start
import urllib

def num_occur(needle, haystack):
    global calls
    calls += 1
    num = 0
    for i in range(len(haystack) - len(needle) + 1):
        if haystack[i : i + len(needle)] == needle:
            num += 1
    return num

calls = 0
url = "https://raw.githubusercontent.com/iatorm/random-data/master/abc_strings.txt"
inputs = urllib.urlopen(url).read().split("\n")
print "Check: ", inputs == map(lambda h: get_that_string(h, len(h)), inputs)
print "Calls: ", calls

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

sort: votes


text:
Output "Fit" numbers
"Fit Numbers"
Sam has a "brilliant" idea for compression! Can you help?

Here is a rundown of Sam's compression scheme. First take in a base 10 representation of any natural number strictly smaller than 2^16, and write it as a binary string without any leading zeros.

1 -> 1
9 -> 1001
15 ->1111
13 ->1101
16 -> 10000
17 -> 10001
65535 -> 111111111111111

Now replace any group of one or more zeros with a single zero. This is because the number has gotten leaner. Your binary string now will look like this.

1 -> 1 -> 1
9 -> 1001 -> 101
15 ->1111 -> 1111
13 ->1101 -> 1101
16 -> 10000 -> 10
17 -> 10001 -> 101
65535 -> 111111111111111 -> 111111111111111

Now you convert the binary string back to a base 10 representation, and output it in any acceptable format. Here are your test cases. The first integer represents an input, and the last integer represents an output. Note that some numbers do not change, and thus can be called "fit"

1 -> 1 -> 1 -> 1
9 -> 1001 -> 101 -> 5
15 ->1111 -> 1111 -> 15
13 ->1101 -> 1101 -> 13
16 -> 10000 -> 10 -> 2
17 -> 10001 -> 101 -> 5
65535 -> 1111111111111111 -> 1111111111111111 -> 65535
65000 -> 1111110111101000 -> 11111101111010 -> 16250

You may use any language, but please note that Sam hates standard loopholes. This is code golf so the code can be as short as possible to make room for the "compressed" numbers".

Note:This is NOT an acceptable compression scheme. Using this will promptly get you fired.

Citation-Needed: I do not take credit for this concept. This comes from @Conor O' Brien's blog here see this OEIS of fit numbers. https://oeis.org/A090078

From @Conor's comic blog: link

OEIS A090078 might come in handy.

It is I who wrote the comic. I also expect a 35% rep royalty ;)

Would the downvoter please explain the issue?

Why is 16 equal to 8? Shouldn't 16 be 10000?

@eithedog 16 goes to 10000, and then you crunch the consecutive zeros down. So 16 goes to 10000 10 goes to 2 and 8 goes to 1000 goes to 10 goes to two

But you wrote 16 -> 1000 -> 10 -> 2. Shouldn't it be 16 -> 10000 -> 10 -> 2?

@Dennis whoops fixing now!

@eithedog my bad

Do we need to convert back to decimal?

The first code block still has 16 and 17 wrong.

@LeakyNun yes you do

@immibis fixing now

05AB1E, 8 6 bytes
b00¬:C

Explanation
b        # convert input to binary
 00¬:    # replace 00 with 0 while possible
     C   # convert to int

Try it online
Saved 2 bytes thanks to Adnan

You can replace „00'0 by 00¬ :).

@Adnan Nice! Didn't think of that.

I don't even know why I explicitly pushed them as strings...

Yeah, it's a bit counterintuitive, but it works :).

This is looking like it will win :D, i'll give it a bit more time before accepting so that more people can participate.

Bash + GNU utilities, 27
dc -e2o?p|tr -s 0|dc -e2i?p

Input read from STDIN.

Nice! I have never used dc :)

The dc man page reads a lot like the docs for some golfing languages.

JavaScript (ES6), 41 bytes
n=>+`0b${n.toString(2).replace(/0+/g,0)}`

Jellyfish, 20 bytes
p
d
# S
,1
*
\dbi
 2

Try it online!
Explanation

i is input.
b converts it to binary (list of digits)
\d with arguments 2 and the digit list applies d (binary digits to number) to every length-2 substring of the digit list.
* takes signum of the results: 00 goes to 0, everything else to 1.
,1 tacks a 1 to the end, so the last digit is not lost.
# S selects from bi those digits which have a 1 on the list computed above: those that are not the left halves of 00.
d converts back to number, and p prints the result.

Python 2, 36 bytes
f=lambda n:n and f(n/2)<<(n%4>0)|n%2

A direct recursive implementation with no base conversion built-ins or string operations. Less golfed:
f=lambda n:n and[f(n/2),n%2+2*f(n/2)][n%4>0]

When n is a multiple of 4, it ends in two 0's in binary, so we cut one by floor-dividing by 2. Otherwise, we split n into (n%2) + 2*(n/2), leave the last binary digit n%2 alone, and recurse on the other digits n/2.

Isn't n%2 redundant?

@xsot Not sure what you mean. Doing |n gives wrong results.

I mean you can replace the whole of (n%4>0)|n%2 with (n%4>0).

@xsot The precedence goes as (f(n/2)<<(n%4>0)) | n%2.

Ah, my bad then. I thought shifting has the lowest precedence.

Bash (sed + bc), 60 55 43 bytes
echo $[2#`bc<<<obase=2\;$1|sed s/00\*/0/g`]

edit:

changed sed -E 's/0+ to sed 's/00* and changed echo and pipe used to pass the value to bc with <<<.
Brilliant suggestion by @Digital Trauma!

example:
$ bash script.sh 65000
16250
$ bash script.sh 15
15
$ bash script.sh 9
5

sed + bc was my first thought too. echo "obase=2;$1"|bc|sed 's/00*/0/g;s/^/ibase=2;/'|bc is 2 bytes shorter

Use pipes and escapes to your advantage: echo $[2#\bc<<<obase=2;$1|sed s/00*/0/g`].  But dcandtr` make it way shorter.

@DigitalTrauma: Thanks, that's great! @Riley: nice idea, it would be a bit shorter like that: bc<<<"obase=2;$1"|sed 's/00*/0/g;s/^/ibase=2;/'|bc

if you use tr -s 0 instead of sed you can get down to 36 bytes

@Riley: True, but Digital Trauma already uses it in the other bash answer so I prefer not to use it :)

Good call, I didn't see his.

Python 3, 55, 50 bytes.
Saved 4 bytes thanks to Sp3000.
Pretty straightforward solution.
import re
f=lambda x:eval(re.sub('0+','0',bin(x)))

Can you keep the 0b and just eval instead?

@Sp3000 Certainly can! Thanks for the suggestion!

Anonymous lambdas are allowed; you can shrink this to 48 bytes by using lambda x:eval(re.sub('0+','0',bin(x))) <insert newline here> import re

MATL, 11 9 8 bytes
BFFOZtXB

This version works only in MATLAB since strrep in MATLAB can handle logical inputs. Here is a version that will work in Octave (9 bytes) (and thus the online interpreter) which explicitly casts the logical inputs to type double.
Try it online
Explanation
    % Implicitly grab input
B   % Convert decimal to binary
FF  % Create the array [0 0]
O   % Number literal
Zt  % Replaces all [0 0] with [0] (will replace any number of 0's with 0)
XB  % Convert binary to decimal
    % Implicitly display

Perl 6,  31  27 bytes
{:2(.base(2).subst(:g,/0+/,0))}
{:2(.base(2)~~{S:g/0+/0/})}
Explanation:
-> $_ {
  # convert from base 2
  :2(

    # convert to base 2
    $_.base(2)

    # substitute
    .subst(
      :global,
      / 0+ /,  # all substrings made of 0s
      '0'      # with one 0
    )
  )
}

Example:
my &fit-compress = {:2(.base(2)~~{S:g/0+/0/})}
say fit-compress 1;     # 1
say fit-compress 9;     # 5
say fit-compress 15;    # 15
say fit-compress 13;    # 13
say fit-compress 16;    # 2
say fit-compress 17;    # 5
say fit-compress 65535; # 65535
say fit-compress 65000; # 16250

# number created with ｢:2( [~] <0 1>.roll: 256 )｣
say fit-compress 80794946326210692074631955353531749442835289622757526957697718534769445507500
# 4240335298301026395935723255481812004519990428936918

Javascript (ES6), 40 bytes
n=>'0b'+n.toString(2).replace(/0+/g,0)-0

I'm afraid this is a snippet. Unless the challenge description states otherwise, the solutions are expected to be either full programs or functions.

What require to be "full program" in Javascript if I don't want to use function? Please advise.

For example with Node.js: console.log(+('0b'+parseInt(process.argv[1]).toString(2).replace(/0+/g,0))).

Off topic. Your code block has the same problem as @Master_ex. Is it because some popular shell config scripts polluting the terminal? Or SE's fault?

The site engine inserts U+200C (zero width non-joiner) and U+200B (zero width space) character pairs in the code part of comments.

The shortest fix would be to prepend N=> which would make it a valid function submission.

Actually, 14 bytes
├`'0;;+(Æ`Y2@¿

Try it online!
Explanation:
├`'0;;+(Æ`Y2@¿
├               bin(input) (automatically discards leading zeroes)
 `'0;;+(Æ`Y     call this function until the output stops changing:
  '0;;+           push "0", "00"
       (Æ         replace "00" with "0" in binary string
           2@¿  convert from binary to decimal

Then post a competing version!

Ruby, 35 31 bytes
-2 bytes thanks to @Doorknob
->n{eval ("0b%b"%n).squeeze ?0}

See it on repl.it: https://repl.it/CnnQ/2

C, 37 bytes
f(x){return x?f(x/2)<<!!(x%4)|x&1:0;}

C#, 112 91 bytes
int x(int x)=>Convert.ToInt32(Regex.Replace(Convert.ToString(x,2),"0+","0"),2);

-8 bytes thanks to TuukkaX

int f(int x){var a=Regex.Replace(Convert.ToString(x,2),"0+","0");return Convert.ToInt32(a,2);} - 94 bytes using regex. I've seen a lot of C# solutions not include System.Text.RegularExpressions so maybe it's allowed here too...?

int f(int x){return Convert.ToInt32(Regex.Replace(Convert.ToString(x,2),"0+","0"),2);} 86 bytes.

i dont know how you are counting bytes, i use this https://mothereff.in/byte-counter

I use that page too, but it wouldn't work, so I used a different page. You should also mention the required C# version.

mothereff.in/byte-counter calculates 79 bytes for your current solution. I had to type the solution by hand, otherwise it would give me 91.

Perl, 38 + 1 (-p) = 39 bytes
$_=oct"0b".sprintf("%b",$_)=~s/0+/0/gr

Needs -p flag to run (I added -l flag to make it more readable, but it's not needed otherwise) :
perl -plE '$_=oct"0b".sprintf("%b",$_)=~s/0+/0/gr' <<< "1
9
15
13
16
17
65535
65000"

Note much to say about the code : it converts the number into binary (sprintf"%b"), then replaces blocs of zeros by just one zero, and converts the result into decimal (oct"0b".).

Java, 75
int f(Integer x){return x.valueOf(x.toString(x,2).replaceAll("0+","0"),2);}

Test program:
public class Fit {
    int f(Integer x){return x.valueOf(x.toString(x,2).replaceAll("0+","0"),2);}

    public static void main(final String... args) {
        final Fit x = new Fit();
        System.out.println(x.f(65000));
    }
}

Java 8 convert to lamda x->blah; for fewer bytes

int f(Integer x){return x.parseInt(x.toString(x,2).replaceAll("0+","0"));} for a couple fewer bytes

@RohanJhunjhunwala That's wrong, it needs to use base 2. As for the lambda, I feel that it's incomplete without the type specification.

oh ok, the other java answer uses the same technique

http://codegolf.stackexchange.com/a/90085/46918

PARI/GP, 54 43 bytes
n->fold((a,b)->a+if(b,a+1,a%2,a),binary(n))

PHP, 53 51 Bytes
<?=bindec(preg_replace("/0+/",0,decbin($argv[1])));

Takes an argument from the console.
Thanks to:
@manatwork replace "0" with 0

Mostly "0" and 0 are handled in the same way.

@manatwork Thanks. That was a pretty obvious one I should have seen myself.

Jelly, 13 7 bytes
6 bytes thanks to Zgarb for his algorithm.

BŒgµL*x@Ḣµ€FḄ
BŒgḄBFḄ

Try it online!

TSQL, 143 bytes
Not using build ins to convert from and to binary.
Golfed:
DECLARE @i INT=65000

,@ CHAR(99)=''WHILE @i>0SELECT @=REPLACE(LEFT(@i%2,1)+@,'00',0),@i/=2WHILE @>''SELECT @i+=LEFT(@,1)*POWER(2,LEN(@)-1),@=STUFF(@,1,1,'')PRINT @i

Ungolfed:
DECLARE @i INT=65000

,@ CHAR(99)=''
WHILE @i>0
  SELECT @=REPLACE(LEFT(@i%2,1)+@,'00',0),@i/=2

WHILE @>''
  SELECT @i+=LEFT(@,1)*POWER(2,LEN(@)-1),@=STUFF(@,1,1,'')

PRINT @i

Fiddle

+1 for not using built ins. My S.I.L.O.S answer (reference implementation)  does the same, but it got downvoted as people didn't think it was a serious competitor.  Is the new line significant?

@RohanJhunjhunwala the new line is not significant. I am counting the characters of the code after the input variable has been defined and assigned a value.

ok amkes sense -

@RohanJhunjhunwala I think it is cool that you use an unconversial language to solve Codegolf questions. It does seem you have unnecessary code to add extra information - probably only in your ungolfed version though. You should always try to provide the shortest code possible, cutting corners and abusing language querks(within the scope of the question). If possible you should provide a fiddle, so muggles me can test it

The ungolfed version contains unnecessary code, but the golfed version contains no additional code. I can transpiler it into java if you want me to test it.

no need for a java version, I find the syntax of S.I.L.O.S fascinating and primitive - reminds me of my old TI99/4A. It will never be able to compete. But that should not prevent it from participating IMHO.

Let us continue this discussion in chat.

CJam, 16
q~2b1+0a%0a*);2b

Try it online
It's quite long due to lack of regex.
Explanation:
q~     read and evaluate the input number
2b     convert to base 2 (array of 1s and 0s)
1+     append a 1 to deal with trailing zeros
0a%    split by [0], dropping empty pieces; only chunks of 1s are left
0a*    join by [0]
);     discard the 1 we appended before
2b     convert back from base 2

CJam, 23 bytes
ri2be`{_:g:>{:g}&}%e~2b

Try it online!
Explanation
ri          e# Read input as an integer
2b          e# Convert to binary
e`          e# Run-length encoding. Gives a nested (2D) array with run-lengths
            e# and binary digits
{           e# This block is mapped over the outer array, i.e. is applied to
            e# each inner array
   _        e#   Duplicate the inner array
  :g        e#   Signum of each element of inner array
  :>        e#   This gives true if second element (digit) is false and first
            e#   element (run-length) is not zero. If so, we need to set that
            e#   run-length to 1
  {:g}&     e#   If that's the case, apply signum to original copy of inner
            e#   array, to make run-length 1
}%          e# End block which is mapped over the outer array
e~          e# Run-length decoding
2b          e# Convert from binary. Implicitly display

Java, 64 bytes
i->{return i.parseInt(i.toString(i,2).replaceAll("0+","0"),2);};

Test Program
public static void main(String[] args) {
    Function<Integer, Integer> function = i -> {
        return i.parseInt(i.toString(i, 2).replaceAll("0+", "0"), 2);
    };

    System.out.println(function.apply(1)); // 1
    System.out.println(function.apply(9)); // 5
    System.out.println(function.apply(15)); // 15
    System.out.println(function.apply(13)); // 13
    System.out.println(function.apply(16)); // 2
    System.out.println(function.apply(17)); // 5
    System.out.println(function.apply(65535)); // 65535
}

Ruby, 37 35 bytes
Saved two bytes thanks to manatwork.
->a{a.to_s(2).gsub(/0+/,?0).to_i 2}

The naive approach. (:

Regarding "0", see the 2nd point in sepp2k's tip. Regarding .to_i(2), where there is no ambiguity on where a parameter belongs, the parentheses are optional.

Reference Implementation in S.I.L.O.S "only" 417 bytes
Golfed
readIO :
i + 1
I = i
z = 1
n = 32
b = n
z = 1
n = b
lbla
n - 1
GOSUB p
j = i
j - p
if j b
if z c
z = 1
GOTO e
lblc
b - 1
if n a
GOTO f
lblb
z = 0
A = a
A + 1000
set A 1
i - p
lble
a + 1
if n a
lblf
q = 1000
e = q
e + b
i = 0
lbl>
d = q
d - e
if d ?
n = b
n - i
GOSUB p
g = get q
g * p
o + g
i + 1
q + 1
GOTO >
lbl?
o / 2
printInt o
GOTO z
funcp
p = 1
Z = n
lblQ
if Z C
GOTO D
lblC
Z - 1
p * 2
GOTO Q
lblD
return
lblz

Here is the reference implementation fully ungolfed. As a bonus feature it outputs the steps needed to come to an answer.
/**
*Reference Implementation in the high quality S.I.L.O.S language.
*/
readIO Enter a number to "compress"
//some declarations
i + 1
I = i
z = 1
//the above is a flag which shows whether or not a zero was last outputted
n = 32
b = n
//maximum number of input bits
printLine Original Binary

lblbinLoop
n - 1
GOSUB pow
j = I
j - p
if j printOne
if z ENDLOOP
print 0
GOTO ENDLOOP
lblprintOne
z = 0
print 1
I - p
lblENDLOOP
if n binLoop

printLine
printLine Binary "Compressed"

z = 1
n = b

lbltopA
n - 1
GOSUB pow
j = i
j - p
if j printAOne
if z DontPrint
z = 1
print 0
GOTO ENDLOOPA
lblDontPrint
b - 1
if n topA
GOTO endOfBin
lblprintAOne
z = 0
print 1
A = a
A + 1000
set A 1
i - p
lblENDLOOPA
a + 1
if n topA

lblendOfBin

printLine
printLine -----------
printLine Base 10 Output
print Out Bits:
printInt b

q = 1000
e = q
e + b
i = 0
lblOutputDec
d = q
d - e
if d DONE
n = b
n - i
GOSUB pow
g = get q
g * p
o + g
i + 1
q + 1
GOTO OutputDec
lblDONE
printLine
printLine ---------
o / 2
printInt o

GOTO funcs
//function declarations must be wrapped in gotoes to avoid the interpreter from complaining (breaking)

/**
*This will store the nth power of two in the "p" variable
*/
funcpow
p = 1
Z = n
lbltop
if Z continue
GOTO end
lblcontinue
Z - 1
p * 2
GOTO top
lblend
return

lblfuncs

By request the transpilation has been deleted. Feel free to view the edit history to recover it, otherwise go to this repo for an interpreter.
Sample output for 65000
Enter a number to "compress"
65000
Original Binary
1111110111101000
Binary "Compressed"
11111101111010
-----------
Base 10 Output
Out Bits:14
---------
16250

Reference implementations should be in the challenge body, not as answers, since they are ungolfed and thus not serious contenders.

Ok, I'll golf it.

I didn't want to bloat up the challenge body with this @Mego

@TimmyD one second I'm golfing it down now

@Mego I have golfed it now

@Dopapp it is a trivial transpilation down to Java

@Dopapp it has been removed

Would the downvoter care to explain the issue with the post so I can correct it or remove it as needed?

PowerShell v2+, 69 bytes
[convert]::ToInt32(([convert]::ToString($args[0],2)-replace'0+',0),2)

(feature-requestA shorter way to convert to/from binary in PowerShell)
Takes input $args[0], uses the .NET built-in [convert]::ToString(int,base) to convert the input integer into a binary base string. That's filtered through the -replace to strip out any runs of one-or-more-zeros to just 0. That resultant string is sent back through the other direction via [convert]::ToInt32(string,base) to turn the binary back into an integer. That integer is left on the pipeline and output is implicit.
Test Cases
PS C:\Tools\Scripts\golfing> 1,9,15,13,16,17,65535,65000|%{"$_ -> " +(.\output-fit-number.ps1 $_)}
1 -> 1
9 -> 5
15 -> 15
13 -> 13
16 -> 2
17 -> 5
65535 -> 65535
65000 -> 16250

Java, 152 143 138 bytes
interface C{static void main(String[]b){Integer i=0;System.out.print(i.parseInt(i.toString(i.parseInt(b[0]),2).replaceAll("0+","0"),2));}}

9 bytes less thanks to @RohanJhunjhunwala. I prefer to keep it as a fully functioning program with main and the like. However, of course it can be golfed more otherwise.
5 bytes less thanks to @LeakyNun's suggestions.

class A{public static void main(String[] a){Integer i;System.out.print(i.parseInt(i.toBinaryString(i.parseInt(a[0])).replaceAll("0+","0"),2));}} for 8 bytes of saving

wrap it in a lambda expression for even more saving and remove class definitions, and your set.

@RohanJhunjhunwala:Ah! The Integer i; part is simple and fantastic!

@RohanJhunjhunwala: Hm.. However it means that Integer should get imported and that adds more bytes to the total program...

interface Z{static void main(String[]b){Integer i=0;System.out.print(i.parseInt(i.toBinaryString(i.parseInt(b[0])).replaceAll("0+","0"),2));}} works like a charm without imports and golfs off 10 bytes

It works, but may produce a warning (as opposed to an error) on most sane IDE's. The thing is, you can always call static methods from a non static context, but you can never call a non-static method from a static context. While using this technique is strongly strongly discouraged in production code, it is legal java.

http://codegolf.stackexchange.com/questions/6671/tips-for-golfing-in-java Is a good read to get more familiar with the lesser known (dare I say shadier) "features" of the java language.

@RohanJhunjhunwala: Yeah, I got a bit confused with my IDE warnings for a moment there. Thanks for the link with the java golf tips. I have spotted it but haven't read it yet. I sure plan to read it though :)

@Master_ex Integer is part of java.lang and so doesn't need to be imported

String[] b -> String[]b

You can use i.toString(123,2) instead of i.toBinaryString(123)

You don't need to convert back to decimal?

@yitzih: Yeah, I got a bit confused at first because of my IDE warnings.
@LeakyNun: It does indeed convert back to decimal. This, the outer parseInt, is for.

interface C{Integer i;static void main(String[]b){System.out.print(i.parseInt(i.toString(i.parseInt(b[0]),2).replaceAll("0+","0"),2));}}

for two bytes off

Pyth, 12
i:.BQ"0+"\02

Online.
  .BQ            # Convert input from base 10 to base 2
 :   "0+"\0      # Replace multiple zeroes with single zero
i          2     # Convert back from base 2 to base 10

Retina, 30 bytes
.+
$*1;
+`(1+)\1
$1;
1;
1
;+
0

Try it online!
And here I thought Retina would be amongst the first answers...

@randomra I'm asking the question OP for clarification

Is Retina  capable of binary to  decimal conversion or binary to unary conversion? I'll except either one so as to not exclude Retina

@RohanJhunjhunwala: Yes, it is

Is it possible to make this convert to unary or decimal? Ideally I would like to see decimal, but I will accept either.

Dyalog APL, 19 bytes
{2⊥⍵/⍨~0 0⍷⍵}2∘⊥⍣¯1

TryAPL online!
This function is really an "atop" of two functions, the first function is:
2∘⊥⍣¯1 the inverse of binary-to-decimal conversion, i.e. binary-from-decimal conversion
 two 2 is bound ∘ to -to-decimal ⊥
 repeat the operation ⍣ negative one time ¯1 (i.e. once, but inverted)
In the second function, the above's binary result is represented by ⍵:
{2⊥⍵/⍨~0 0⍷⍵}
 0 0⍷⍵ Boolean for where {0, 0} begins in ⍵
 ~ Boolean negation, so now we have ᴛʀᴜᴇ everywhere but at non-first zeros in zero-runs
 ⍵/⍨ use that to filter ⍵, so this removes our unwanted zeros
 2⊥ convert binary-to-decimal

S.I.L.O.S, 120 bytes
readIO
p = 1
lbla
m = i
m % 2
M = m
M - 1
M * F
M + 2
p * M
F = 1
F - m
A = p
A * m
r + A
i / 2
if i a
r / 2
printInt r

Try it online!
This is basically a state machine.

p for the current power
m for the result of the modulo by 2
M for the multiplier (to the power); if we are stuck at zeroes, the multiplier would be 1
F for the flag, to denote whether the zero is the first zero in the run.
r for the result, which is printed at the end.

The conversion between m, M and F is as follows:

m=0, F=0 -> F=1, M=2 (first zero, multiply by 2 anyway)
m=0, F=1 -> F=1, M=1 (not the first zero, multiply by 1)
m=1, F=0 -> F=0, M=2 (it is a one, multiply by 2, reset flag)
m=1, F=1 -> F=0, M=2 (it is a one, multiply by 2, reset flag)

Essentially we come up with the following formula:

M=((m-1)*F)+2
F=1-m

Wow, that golf. So much shorter than the reference

Oasis, 25 bytes (non-competing)
n2÷an»»n»4÷xx-p>*nn2÷x-+0

Try it online!
I have not failed my master. \o/
There are many missing features which must be built. For example, there is no conditionals, so the formula I am using would be f(n/2)*[1+(n%4>0)] + n%2.
Actually, there is no modulo either, so n%2 is implemented as n-(n/2*2) where / is integer division.
I did not mention n%4, because there is no > either. The > in the code means +1. So, n%4>0 is built from is_prime(((n+2)%4)+2) where the modulo is generated as above.

Husk, 11 10 9 bytes
ḋṁS↑o→Σgḋ

Try it online!
-1 byte from H.PWiz.
-1 byte from Jo King.
Alternative 9-byter
ḋṁ?uIΛ¬gḋ

Try it online!
Explanation
ḋṁ?uIΛ≠1gḋ
         ḋ get binary digits
        g  group equal runs of digits
 ṁ         map each group to the following, and concatenate:
  ?  Λ≠1   if all elements are not equal to 1
   u       uniquify the group
    I      else leave it as is
ḋ          convert back to base-10

J-uby, 29 bytes
Based on my Ruby answer.
:%&"0b%b"|~:squeeze&?0|-:eval

Attempt This Online!

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/